Finding long cycles in graphs.
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.
Marinari
Enzo
E
Dipartimento di Fisica and INFN, Sapienza Università di Roma, P. A. Moro 2, 00185 Roma, Italy.
Semerjian
Guilhem
G
Van Kerrebroeck
Valery
V