Phys. Rev. E 75, 066708 (2007) [10 pages]Finding long cycles in graphsReceived 27 February 2007; published 29 June 2007 We analyze the problem of discovering long cycles inside a graph. We propose and test two algorithms for this task. The first one is based on recent advances in statistical mechanics and relies on a message passing procedure. The second follows a more standard Monte Carlo Markov chain strategy. Special attention is devoted to Hamiltonian cycles of (nonregular) random graphs of minimal connectivity equal to 3. © 2007 The American Physical Society URL:
http://link.aps.org/doi/10.1103/PhysRevE.75.066708
DOI:
10.1103/PhysRevE.75.066708
PACS:
02.70.−c, 02.10.Ox, 89.75.Hc
|
|
About | Terms and Conditions | Subscriptions | Search | Help
Use of the American Physical Society websites and journals implies that the user has read and agrees to our Terms and Conditions and any applicable Subscription Agreement. Physical Review®, Physical Review Letters®, Reviews of Modern Physics®, and Physical Review Special Topics® are trademarks of the American Physical Society.