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

DOI10.1007/978-3-319-39817-4_19zbMath1475.68251OpenAlexW2500678779MaRDI QIDQ4632185

Xinwen Jiang, Wei Peng, Dong-Xia Wang

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

phase transitionNP-completenessempirical studyHamiltonian cycle problem

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Asymptotic and finite size parameters for phase transitions: Hamiltonian circuit as a case study
• Generalizations of Dirac's theorem in Hamiltonian graph theory -- a survey
• New sufficient conditions for cycles in graphs
• Limit distribution for the existence of Hamiltonian cycles in a random graph
• Finding Hamilton cycles in sparse random graphs
• An algorithm for finding Hamilton paths and cycles in random graphs
• An Effective Algorithm for and Phase Transitions of the Directed Hamiltonian Cycle Problem
• Critical Behavior in the Satisfiability of Random Boolean Expressions
• Clutter percolation and random graphs
• Determining computational complexity from characteristic ‘phase transitions’
• Gibbs states and the set of solutions of random constraint satisfaction problems