A Vertex Elimination Algorithm for Enumerating all Simple Paths in a Graph
- 1 April 1975
- Vol. 5 (2) , 151-177
- https://doi.org/10.1002/net.1975.5.2.151
Abstract
If a suitable definition of sum and multiplication between sets of paths is given, the sets of all simple paths between all pairs of vertices in a graph can be characterized as the solution of a system of linear equations. The well‐known matrix technique for enumerating such paths corresponds to an iterative solution of this system. A new and more efficient algorithm is here described and analyzed which finds all simple paths by a vertex elimination technique similar to Jordan's method for matrix inversion. Experimental results about a FORTRAN implementation of the algorithm are finally reported.Keywords
This publication has 6 references indexed in Scilit:
- A Boolean algebra method for computing the terminal reliability in a communication networkIEEE Transactions on Circuit Theory, 1973
- On finding the simple paths and circuits in a graphIEEE Transactions on Circuit Theory, 1968
- All paths through a mazeProceedings of the IEEE, 1967
- Algorithm 97: Shortest pathCommunications of the ACM, 1962
- A Theorem on Boolean MatricesJournal of the ACM, 1962
- Regular Expressions and State Graphs for AutomataIEEE Transactions on Electronic Computers, 1960