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