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).
→BibTeX
Abstract
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.
Last update: September 14, 2009.