Finding long cycles in graphs
Authors:
- 29 June 2007
- journal article
- research article
- Published by American Physical Society (APS) in Physical Review E
- Vol. 75 (6) , 066708
Abstract
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.Keywords
All Related Versions
This publication has 30 references indexed in Scilit:
- Statistics of cycles in large networksPhysical Review E, 2006
- An algorithm for counting circuits: Application to real-world and random graphsEurophysics Letters, 2006
- Statistics of cycles: how loopy is your network?Journal of Physics A: General Physics, 2005
- Survey propagation: An algorithm for satisfiabilityRandom Structures & Algorithms, 2005
- Statistical mechanics of complex networksReviews of Modern Physics, 2002
- Generating and Counting Hamilton Cycles in Random Regular GraphsJournal of Algorithms, 1996
- Aging without disorder on long time scalesZeitschrift für Physik B Condensed Matter, 1995
- Almost all regular graphs are hamiltonianRandom Structures & Algorithms, 1994
- Optimization by Simulated AnnealingScience, 1983
- A Probabilistic Proof of an Asymptotic Formula for the Number of Labelled Regular GraphsEuropean Journal of Combinatorics, 1980