[Haskell-cafe] Breaking cycles in a directed graph.
jens.fisseler at FernUni-Hagen.de
Thu Jul 13 03:17:46 EDT 2006
> > 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
More information about the Haskell-Cafe