Hi Daniel,
I want to detect all cycles within the graph and 'break' them by inserting a minimal number of nodes that are labelled with a special cycle-breaker label.
Can anyone give me advice on a good algorithm for finding the cycles and finding the optimum edges to insert the cycle-breaking nodes on?
I've had a similar problem as I needed to find all (even-length) cycles in an undirected graph. To the best of my knowledge the algorithm, described in R.C. Read, R.E. Tarjan. Bounds on Backtrack Algorithms for Listing Cycles, Paths and Spanning Trees. Networks 5: 237-252, 1975, has the (currently) best known running time of O(V+E+EN), N being the number of cycles found. As the algorithm is not that easy to understand (at least for me), you should perhaps have a look at section 8.3, "Cycles", of Edward M. Reingold, Jurg Nievergelt, Narsing Deo. Combinatorial Algorithms: Theory and Practice. Prentice-Hall, Englewood Cliffs, 1977. The algorithm described there is easier to understand and implement. 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. -- Hope this helps, Jens