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.
Keywords
Ackermann functionGaussian eliminationAxiomMathematicsPath (computing)GeneralizationLongest path problemInverseDiscrete mathematicsCombinatoricsGaussianComputer scienceChordal graphGraph
Related Publications
Covariance selection for nonchordal graphs via chordal embedding
We describe algorithms for maximum likelihood estimation of Gaussian graphical models with conditional independence constraints. This problem is also known as covariance selecti...
An Efficient Heuristic Procedure for Partitioning Graphs
We consider the problem of partitioning the nodes of a graph with costs on its edges into subsets of given sizes so as to minimize the sum of the costs on all edges cut. This pr...
Random graphs with arbitrary degree distributions and their applications
Recent work on the structure of social networks and the internet has focused attention on graphs with distributions of vertex degree that are significantly different from the Po...
MOEA/D: A Multiobjective Evolutionary Algorithm Based on Decomposition
Decomposition is a basic strategy in traditional multiobjective optimization. However, it has not yet been widely used in multiobjective evolutionary optimization. This paper pr...
Methods of conjugate gradients for solving linear systems
An iterative algorithm is given for solving a system Ax=k of n linear equations in n unknowns. The solution is given in n steps. It is shown that this method is a special case o...
Publication Info
- Year
- 1975
- Type
- article
- Citations
- 25
- Access
- Closed
External Links
Citation Metrics
25
OpenAlex
Cite This
Robert E. Tarjan
(1975).
Solving path problems on directed graphs..
Munich Personal RePEc Archive (Ludwig Maximilian University of Munich)
.