Abstract
Path Problems in Graphs. A large variety of problems in computer science can be viewed from a common viewpoint as instances of “algebraic” path problems. Among them are of course path problems in graphs such as the shortest path problem or problems of finding optimal paths with respect to more generally defined objective functions; but also graph problems whose formulations do not directly involve the concept of a path, such as finding all bridges and articulation points of a graph. Moreover, there are even problems which seemingly have nothing to do with graphs, such as the solution of systems of linear equations, partial differentiation, or the determination of the regular expression describing the language accepted by a finite automaton.
We describe the relation among these problems and their common algebraic foundation.
We survey algorithms for solving them: vertex elimination algorithms such as Gauß-Jordan elimination; and iterative algorithms such as the “classical” Jacobi and Gauß-Seidel iteration.
AMS 1980 mathematics subject classification (1985 revision): 68–01, (68E10, 68R10, 68Q, 05C, 65-01, 65F05, 65F10, 16A78, 90C35, 90C50).
Zusammenfassung
Wegeprobleme in Graphe. Es gibt eine Vielfalt von Problemen, die sich als “algebraische” Wege-Probleme interpretieren lassen. Dazu gehören natürlich Wege-Probleme auf Graphen wie das gewöhnliche kürzeste-Wege-Problem oder das Bestimmen bester Wege unter allgemeineren Optimalltätskriterien, aber auch Probleme, deren Definition nur indirekt mit Wegen zu tun hat, wie das Bestimmen aller Brücken und Artikulationsknoten eines Graphen. Sogar einige Probleme, die anscheinend überhaupt nichts mit Graphen zu tun haben, lassen sich als algebraische Wege-Probleme behandeln: Man kann z. B. lineare Gleichungssysteme lösen, auf schnellem Weg alle partiellen Ableitungen eines Ausdrucks berechnen, oder einen regulären Ausdruck für die formale Sprache bestimmen, die ein endlicher Automat akzeptiert.
In dieser Überblicksarbeit wird einerseits dargestellt, wie man alle diese Problem unter einen Hut bringt, indem man eine gemeinsame algebraische Formulierung für sie findet; andererseits werden verschiedene Lösungsalgorithmen besprochen: Knoteneliminations-Algorithmen (z. B. Gauß-Jordan-Elimination) und iterative Algorithmen (wie die klassischen Iterationsverfahren von Jacobi und Gauß-Seidel).
This work was written while the author was at the Freie Universitat Berlin, Fachbereich Mathematik. It was partially supported by the ESPRIT II Basic Research Action Program of the EC under contract no. 3075 (project ALCOM).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
S. K. Abdali and B. D. Saunders, Transitive closure and related semiring properties via eliminants, Theoret. Comput. Sci. 40 (1985), 257–274.
A. V. Aho, J. E. Hopcroft, and J. D. Ullman, The Design and Analysis of Computer Algorithms, Addison-Wesley, Reading (Mass.) etc. 1974.
W. Baur and V. Strassen, The complexity of partial derivatives, Theoret. Comput. Sci. 22 (1983), 317–330.
B. A. Carré, Graphs and Networks, The Clarendon Press, Oxford University Press, Oxford 1979.
G. N. Frederickson and D. B. Johnson, The complexity of selection and ranking in X + Y and matrices with sorted columns, J. Comput. Syst. Sci. 24 (1982), 197–208.
M. Gondran and M. inoux, Graphes gorithmes, Editions Eyrolles, Paris 1979; English translation: Graphs and Algorithms, Wiley, Chichester etc. 1984.
M. Iri, Simultaneous computation of functions, partial derivatives, and estimates of rounding errors, Japan J. Appl. Math. 1 (1984), 223–252.
M. Iri and K. Kubota, Methods of fast automatic differentiation and applications, Research Memorandum RMI87–02, University of Tokyo, Faculty of Engineering, Hongo 7–3-1, Bunkyo-ku, Tokyo, July 1987.
D. J. Lehmann, Algebraic structures for transitive closure, Theoret. Comput. Sci. 4 (1977), 59–66.
R. J. Lipton, D. J. Rose, and R. E. Tarjan, Generalized nested dissection, SLAM J. Numer. Anal. 16 (1979), 346–358.
R. J. Lipton and R. E. Tarjan, A separator theorem for planar graphs, SIAM J. Appl. Math. 36 (1979), 177–189.
B. Mahr, Iteration and summability in semirings, in: R. E. Burkard, R. A. Cuninghame-Green, U. Zimmermann (eds.), Algebraic and Combinatorial Methods in Operations Research (Proc. Workshop on Algebraic Structures in Operations Research, Bad Honnef, Germany, April 1982), Annals of Discrete Mathematics 19, North-Holland, Amsterdam 1984, pp. 229–256.
G. Rote, A systolic array for the algebraic path problem, Computing 34 (1985), 191–219.
J. W. Sawyer, Jr., Fast partial differentiation by computer with an application to categorical data analysis, The American Statistician 38 (1984), 300–308.
R. E. Tarjan, A unified approach to path problems, J. Assoc. Comput. Mach. 28 (1981), 577–593.
R. E. Tarjan, Fast algorithms for solving path problems, J. Assoc. Comput. Mach. 28 (1981), 594–614.
U. Zimmermann, Linear and combinatorial optimization in order algebraic structures, Annals of Discrete Mathematics 10, North-Holland, Amsterdam 1981.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1990 Springer-Verlag
About this chapter
Cite this chapter
Rote, G. (1990). Path Problems in Graphs. In: Tinhofer, G., Mayr, E., Noltemeier, H., Syslo, M.M. (eds) Computational Graph Theory. Computing Supplementum, vol 7. Springer, Vienna. https://doi.org/10.1007/978-3-7091-9076-0_9
Download citation
DOI: https://doi.org/10.1007/978-3-7091-9076-0_9
Publisher Name: Springer, Vienna
Print ISBN: 978-3-211-82177-0
Online ISBN: 978-3-7091-9076-0
eBook Packages: Springer Book Archive