Finding long cycles in graphs

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.

References in corpus (11)

• Statistical mechanics of complex networks
• Random graphs with arbitrary degree distributions and their applications
• Simulated Tempering: A New Monte Carlo Scheme
• The random K-satisfiability problem: from an analytic solution to an efficient algorithm
• On large deviation properties of Erdos-Renyi random graphs
• Loops structure of the Internet at the Autonomous System Level
• Statistics of Cycles: How Loopy is your Network?
• An algorithm for counting circuits: application to real-world and random graphs
• Aging without disorder on long time scales
• Statistics of cycles in large networks
• Sudden emergence of q-regular subgraphs in random graphs

Cited by in corpus (9)

• Spin glass approach to the feedback vertex set problem
• Belief-Propagation for Weighted b-Matchings on Arbitrary Graphs and its Relation to Linear Programs with Integer Solutions
• Networking - A Statistical Physics Perspective
• Distribution of shortest cycle lengths in random networks
• Ranking by Loops: a new approach to categorization
• Statistical analysis of articulation points in configuration model networks
• Percolation and Loop Statistics in Complex Networks
• Stochastic and mixed flower graphs
• Unevenness of Loop Location in Complex Networks