1
$\begingroup$

I have a strongly connected component with over 200 vertices and more than 600 edges. I need to iterate through each simple cycle in the graph exhaustively, without specifying a particular node. Is there any efficient algorithm to perform this operation?

$\endgroup$
2
$\begingroup$

Efficient Algorithms are already known in the literature.

See e.g.,

  • Tarjan, R E and Read, R C (1975) Bounds on backtrack algorithms for listing cycles, paths, and spanning trees. Networks 5(3):237-252

  • Johnson, D. B. (1975) Finding All the Elementary Circuits of a Directed Graph. SIAM Journal on Computing 4(1):77-84.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.