An Efficient Search Algorithm to Find the Elementary Circuits of a Graph

A theoretically most efficient search algorithm is presented
which 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.  The speed is also related to the number of circuits
in the graph to give a relation between speed and complexity.
Extensions to undirected and s-graphs are discussed.

CACM December, 1970

Tiernan, J. C.

algorithm, graph theory, circuit search
algorithm, path search algorithm, searching

3.74 5.32

CA701202 JB February 9, 1978 4:12 PM

1847	4	1961
1961	4	1961
1961	4	1961
1961	4	1961
2052	4	1961
2177	4	1961
2763	4	1961
1369	5	1961
1504	5	1961
1847	5	1961
1961	5	1961
1961	5	1961
1961	5	1961
2430	5	1961
1961	6	1961