[Haskell-cafe] Breaking cycles in a directed graph.

Daniel McAllansmith dm.maillists at gmail.com
Wed Jul 12 19:31:41 EDT 2006

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.


More information about the Haskell-Cafe mailing list