Finding long cycles in graphs

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

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

Statistical Mechanics, Disordered Systems and Neural Networks, Computational Complexity, Probability

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/132829

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/cond-mat/0702613
 http://arxiv.org/abs/cond-mat/0702613
 Phys. Rev. E 75, 066708 (2007)
 doi:10.1103/PhysRevE.75.066708

Collections

arXiv