Finding All the Elementary Circuits of a Directed Graph
- 1 March 1975
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 4 (1), 77-84
- https://doi.org/10.1137/0204007
Abstract
An algorithm is presented which finds all the elementary circuits-of a directed graph in time bounded by O((n + e)(c + 1)) and space bounded by O(n + e), where there are n vertices, e edges and c elementary circuits in the graph. The algorithm resembles algorithms by Tiernan and Tarjan, but is faster because it considers each edge at most twice between any one circuit and the next in the output sequence.Keywords
This publication has 4 references indexed in Scilit:
- Enumeration of the Elementary Circuits of a Directed GraphSIAM Journal on Computing, 1973
- Depth-First Search and Linear Graph AlgorithmsSIAM Journal on Computing, 1972
- A New Search Algorithm for Finding the Simple Cycles of a Finite Directed GraphJournal of the ACM, 1972
- An efficient search algorithm to find the elementary circuits of a graphCommunications of the ACM, 1970