1. An Efficient Search Algorithm to Find the Elementary Circuits of a Graph.
- Author
-
Tiernan, James C.
- Subjects
- *
ALGORITHMS , *ALGEBRA , *LOGIC circuits , *COMPUTER circuits , *GRAPH theory , *COMPUTER science - Abstract
A theoretically most efficient search algorithm is presented width uses an exhaustive search to find all of the elementary circuits of a graph. The algorithm can be easily modified to find all of the elementary circuits with a particular attribute such as length. A rigorous proof of the algorithm is given as well as an example of Its application. Empirical bounds are presented relating the speed of the algorithm to the number of vertices and the number of arcs. Th. speed is also related to the number of circuits in th. graph to give a relation between speed and complexity. Extensions to undirected and s-graphs are discussed. [ABSTRACT FROM AUTHOR]
- Published
- 1970
- Full Text
- View/download PDF