Günter Rote:

Path problems in graphs

In: "Computational Graph Theory". Editors: G. Tinhofer, E. Mayr, H. Noltemeier, and M. Syslo, in cooperation with R. Albrecht. Springer-Verlag, 1990. Computing Supplementum 7 (1990), pp. 155–189, (Zbl 699.68088, MR #91m:05122).


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.

  PostScript file (gzipped)   pdf file (gzipped)   TeX .dvi file (gzipped)
other papers about this subject
Last update: September 14, 2009.