Empirical Study of Phase Transition of Hamiltonian Cycle Problem in Random Graphs with Degrees Greater Than One

DOI10.1007/978-3-319-39817-4_19MaRDI QIDQ4632185zbMATH OpenOpenAlexFDO

Authors Wei Peng, Dong-Xia Wang, Xinwen Jiang

Publication date 26 April 2019

Published in Frontiers in Algorithmics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-39817-4_19

zbMATH Keywords

empirical studyHamiltonian cycle problemNP-completenessphase transition

Mathematics Subject Classification ID

Eulerian and Hamiltonian graphs (05C45) Random graphs (graph-theoretic aspects) (05C80) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• scientific article; zbMATH DE number 1249657
• Random graph's Hamiltonicity is strongly tied to its minimum degree
• Finding Hamilton cycles in sparse random graphs
• An effective algorithm for and phase transitions of the directed Hamiltonian cycle problem
• Random instances of problems in NP -- algorithms and statistical physics

Cites work

• An algorithm for finding Hamilton paths and cycles in random graphs
• An effective algorithm for and phase transitions of the directed Hamiltonian cycle problem
• Asymptotic and finite size parameters for phase transitions: Hamiltonian circuit as a case study
• Clutter percolation and random graphs
• Critical Behavior in the Satisfiability of Random Boolean Expressions
• Determining computational complexity from characteristic ``phase transitions
• Finding Hamilton cycles in sparse random graphs
• Generalizations of Dirac's theorem in Hamiltonian graph theory -- a survey
• Gibbs states and the set of solutions of random constraint satisfaction problems
• scientific article; zbMATH DE number 67483 (Why is no real title available?)
• scientific article; zbMATH DE number 1249657 (Why is no real title available?)
• scientific article; zbMATH DE number 2084703 (Why is no real title available?)
• scientific article; zbMATH DE number 1448978 (Why is no real title available?)
• scientific article; zbMATH DE number 2243360 (Why is no real title available?)
• Limit distribution for the existence of Hamiltonian cycles in a random graph
• New sufficient conditions for cycles in graphs

Cited in

(1)

• scientific article; zbMATH DE number 1249657 (Why is no real title available?)

This page was built for publication: Empirical Study of Phase Transition of Hamiltonian Cycle Problem in Random Graphs with Degrees Greater Than One

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4632185)