Solving Path Problems on Directed Graphs
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 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.
Document Details
- Document Type
- Technical Report
- Publication Date
- Nov 01, 1975
- Accession Number
- ADA020597
Entities
People
- Robert Tarjan
Organizations
- Stanford University