Asymptotic and finite size parameters for phase transitions: Hamiltonian circuit as a case study

DOI10.1016/S0020-0190(97)00222-6MaRDI QIDQ293254zbMATH OpenFDO

Authors Jeremy Frank, Toby Walsh, Ian P. Gent

Publication date 9 June 2016

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL http://www.sciencedirect.com/science/article/pii/S0020019097002226?np=y

zbMATH Keywords

analysis of algorithmscomputational complexityconstrainednessfinite size scalingphase transitions

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Refining the phase transition in combinatorial search
• Complexity-theoretic models of phase transitions in search problems
• scientific article; zbMATH DE number 67483
• The TSP phase transition
• An empirical study of phase transitions in binary constraint satisfaction problems

Cites work

• Algorithm 595: An Enumerative Algorithm for Finding Hamiltonian Circuits in a Directed Graph
• Critical Behavior in the Satisfiability of Random Boolean Expressions
• Easy problems are sometimes hard
• Fast probabilistic algorithms for Hamiltonian circuits and matchings
• scientific article; zbMATH DE number 67483 (Why is no real title available?)
• scientific article; zbMATH DE number 3549021 (Why is no real title available?)
• scientific article; zbMATH DE number 3193293 (Why is no real title available?)
• The hardest constraint problems: A double phase transition
• The main properties of random graphs with a large number of vertices and edges
• The TSP phase transition

Cited in

(3)

• SAT problems with chains of dependent variables
• Refining the phase transition in combinatorial search
• Empirical study of phase transition of Hamiltonian cycle problem in random graphs with degrees greater than one

This page was built for publication: Asymptotic and finite size parameters for phase transitions: Hamiltonian circuit as a case study

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