Finding long cycles in graphs
Authors:
- Enzo MarinariEMEnzo Marinari
- Guilhem SemerjianGSGuilhem Semerjian
- Valery Van KerrebroeckVKValery Van Kerrebroeck
Preprint
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 (non-regular) random graphs of minimal connectivity equal to three.Keywords
All Related Versions
- Version 1, 2007-02-26, ArXiv
- Published version: Physical Review E, 75 (6), 066708.