On Wednesday 12 July 2006 19:19, Jens Fisseler wrote:
R.C. Read, R.E. Tarjan. Bounds on Backtrack Algorithms for Listing Cycles, Paths and Spanning Trees. Networks 5: 237-252, 1975,
section 8.3, "Cycles", of Edward M. Reingold, Jurg Nievergelt, Narsing Deo. Combinatorial Algorithms: Theory and Practice. Prentice-Hall, Englewood Cliffs, 1977.
You can also find a survey in
Prabhaker Mateti, Narsing Deo. On Algorithms for Enumerating All Circuits of a Graph. SIAM Journal on Computing, 5(1): 90-99, 1976.
Hi, Jens. You don't know if there is an overview, or implementation, of these algorithms online do you? I don't have (easy) access to these references. Another that might be applicable is: Donald B. Johnson. Finding all the elementary circuits of a directed graph. SIAM J. Comput, 5:77--84, 1975. Though I don't have access to that either. Also I gather Combinatorica, a Mathematica module, has algorithms covering this sort of thing. I understand it has a restrictive licence so I haven't looked at those either. Thanks Daniel