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

[Jens Fisseler]

Hi Daniel,

> > 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.

Johnson's algorithm is the one described in the book by Reingold et al.
I have only hardcopies of all references, although I have a
PROLOG-implementation of Tarjan's algorithm.

One possibility would be to scan the hardcopies and send them to you by
e-mail.

Regards,

	Jens