[Haskell-cafe] Breaking cycles in a directed graph.
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.
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