Jove
Visualize
Contact Us
JoVE
x logofacebook logolinkedin logoyoutube logo
ABOUT JoVE
OverviewLeadershipBlogJoVE Help Center
AUTHORS
Publishing ProcessEditorial BoardScope & PoliciesPeer ReviewFAQSubmit
LIBRARIANS
TestimonialsSubscriptionsAccessResourcesLibrary Advisory BoardFAQ
RESEARCH
JoVE JournalMethods CollectionsJoVE Encyclopedia of ExperimentsArchive
EDUCATION
JoVE CoreJoVE BusinessJoVE Science EducationJoVE Lab ManualFaculty Resource CenterFaculty Site
Terms & Conditions of Use
Privacy Policy
Policies

Related Experiment Videos

Finding long cycles in graphs.

Enzo Marinari1, Guilhem Semerjian, Valery Van Kerrebroeck

  • 1Dipartimento di Fisica and INFN, Sapienza Università di Roma, P. A. Moro 2, 00185 Roma, Italy.

Physical Review. E, Statistical, Nonlinear, and Soft Matter Physics
|August 7, 2007
PubMed
Summary
This summary is machine-generated.

Related Concept Videos

You might also read

Related Articles

Articles linked to this work by shared authors, journal, and citation graph.

Sort by
Same author

Discrete-space and -time analog of a super-diffusive fractional Brownian motion.

Chaos (Woodbury, N.Y.)·2025
Same author

Diffusion reconstruction for the diluted Ising model.

Physical review. E·2025
Same author

Multifractality in spin glasses.

Proceedings of the National Academy of Sciences of the United States of America·2024
Same author

Spectral fingerprints of nonequilibrium dynamics: The case of a Brownian gyrator.

Physical review. E·2022
Same author

Supervised perceptron learning vs unsupervised Hebbian unlearning: Approaching optimal memory retrieval in Hopfield-like networks.

The Journal of chemical physics·2022
Same author

Recognition capabilities of a Hopfield model with auxiliary hidden neurons.

Physical review. E·2021
Same journal

Tension on dsDNA bound to ssDNA-RecA filaments may play an important role in driving efficient and accurate homology recognition and strand exchange.

Physical review. E, Statistical, nonlinear, and soft matter physics·2016
Same journal

Publisher's Note: Amplitude-phase coupling drives chimera states in globally coupled laser networks [Phys. Rev. E 91, 040901(R) (2015)].

Physical review. E, Statistical, nonlinear, and soft matter physics·2016
Same journal

Erratum: Shapes of sedimenting soft elastic capsules in a viscous fluid [Phys. Rev. E 92, 033003 (2015)].

Physical review. E, Statistical, nonlinear, and soft matter physics·2016
Same journal

Erratum: Attenuation of excitation decay rate due to collective effect [Phys. Rev. E 90, 022142 (2014)].

Physical review. E, Statistical, nonlinear, and soft matter physics·2016
Same journal

Publisher's Note: Role of connectivity and fluctuations in the nucleation of calcium waves in cardiac cells [Phys. Rev. E 92, 052715 (2015)].

Physical review. E, Statistical, nonlinear, and soft matter physics·2016
Same journal

Publisher's Note: Lattice Boltzmann approach for complex nonequilibrium flows [Phys. Rev. E 92, 043308 (2015)].

Physical review. E, Statistical, nonlinear, and soft matter physics·2016
See all related articles

This study introduces two novel algorithms for finding long cycles in graphs, including Hamiltonian cycles in random graphs. These methods leverage statistical mechanics and Monte Carlo strategies for efficient graph analysis.

Area of Science:

  • Graph theory
  • Statistical mechanics
  • Computational complexity

Background:

  • Discovering long cycles in graphs is a computationally challenging problem.
  • Hamiltonian cycles are of particular interest in various scientific domains.
  • Random graphs with specific connectivity properties present unique analytical difficulties.

Purpose of the Study:

  • To develop and evaluate algorithms for identifying long cycles in graphs.
  • To specifically address the challenge of finding Hamiltonian cycles in random graphs with minimal connectivity.

Main Methods:

  • A message-passing algorithm inspired by statistical mechanics.
  • A standard Monte Carlo Markov chain approach.
  • Analysis focused on random graphs with a minimal connectivity of 3.

Related Experiment Videos

Main Results:

  • The proposed algorithms demonstrate effectiveness in discovering long cycles.
  • Performance is evaluated on random graphs, with a focus on Hamiltonian cycles.
  • The statistical mechanics approach offers a novel perspective on cycle discovery.

Conclusions:

  • The developed algorithms provide viable solutions for the long cycle discovery problem.
  • The study contributes to the understanding of Hamiltonian cycles in specific random graph structures.
  • Future work can explore optimizations and applications of these graph algorithms.