Enumeration of the Elementary Circuits of a Directed Graph
- 1 September 1973
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 2 (3), 211-216
- https://doi.org/10.1137/0202017
Abstract
An algorithm to enumerate all the elementary circuits of a directed graph is presented. The algorithm uses back-tracking with lookahead to avoid unnecessary work, and it has a time bound of $O ((V+E)(C+1))$ when applied to a graph with $V$ vertices, $E$ edges, and $C$ elementary circuits. Keywords: Algorithm, circuit, cycle, graph
Keywords
This publication has 3 references indexed in Scilit:
- 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