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.