Report Number: CS-TR-75-528
Institution: Stanford University, Department of Computer Science
Title: Solving path problems on directed graphs.
Author: Tarjan, Robert Endre
Date: October 1975
Abstract: 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 O($n^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. This method is a generalization of the "reducibility" notion of data flow analysis, and is a kind of single-element "tearing". Efficiently implemented, the method requires O(m $\alpha$(m,n)) time plus time to solve the subproblems, for problem graphs with n vertices and m edges. Here $\alpha$(m,n) is a very slowly growing function which is a functional inverse of Ackermann's function. 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.
http://i.stanford.edu/pub/cstr/reports/cs/tr/75/528/CS-TR-75-528.pdf