Solving path problems on directed graphs.
Robert Endre Tarjan · Defense Technical Information Center (DTIC) · 1975
This paper considers path problems on directed graphs which are solvable by a method similar to Gaussian elimination. The paper gives an axiom system for such problems which is a weakening of Salomaa's axioms for a regular algebra. The paper presents a general solution method which requires 0(n sup 3) time for dense graphs with n vertices and considerably less time for sparse graphs. The paper also presents a decomposition method which solves a path problem by breaking it into subproblems, solving each subproblem by elimination, and combining the solutions. The paper considers variants of the axiom system for which the solution methods still work, and presents several applications, including solving simultaneous linear equations and analyzing control flow in computer programs.