The hardest constraint problems: A double phase transition

DOI10.1016/0004-3702(94)90088-4MaRDI QIDQ1337687zbMATH OpenOpenAlexFDO

Authors Tad Hogg, Colin P. Williams

Publication date 26 February 1996

Published in Artificial Intelligence (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0004-3702(94)90088-4

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15)

Cites work

• scientific article; zbMATH DE number 3902655 (Why is no real title available?)
• scientific article; zbMATH DE number 3769673 (Why is no real title available?)
• scientific article; zbMATH DE number 67483 (Why is no real title available?)
• scientific article; zbMATH DE number 3273551 (Why is no real title available?)
• scientific article; zbMATH DE number 956853 (Why is no real title available?)
• Easy problems are sometimes hard
• Exploiting the deep structure of constraint problems
• Optimization by Simulated Annealing: An Experimental Evaluation; Part II, Graph Coloring and Number Partitioning

Cited in

(30)

• Average-case complexity of backtrack search for coloring sparse random graphs
• Computation with polynomial equations and inequalities arising in combinatorial optimization
• Complexity studies of a temporal constraint propagation algorithm: a statistical analysis
• Accelerating backtrack search with a best-first-search strategy
• Towards a practical engineering tool for rostering
• Statistical regimes across constrainedness regions
• The satisfiability constraint gap
• A Model to Study Phase Transition and Plateaus in Relational Learning
• Frozen development in graph coloring
• Constructive generation of very hard 3-colorability instances
• Empirically-derived estimates of the complexity of labeling line drawings of polyhedral scenes
• Experimental complexity analysis of continuous constraint satisfaction problems.
• An improved upper bound on the non-3-colourability threshold
• An empirical study of phase transitions in binary constraint satisfaction problems
• Experimental results on the crossover point in random 3-SAT
• Asymptotic and finite size parameters for phase transitions: Hamiltonian circuit as a case study
• Complexity of coloring random graphs: an experimental study of the hardest region
• Phase transitions and the search problem
• The impact of search heuristics on heavy-tailed behaviour
• Implicates and prime implicates in random 3-SAT
• A generative power-law search tree model
• Critical behavior in the computational cost of satisfiability testing
• Refining the phase transition in combinatorial search
• Easy problems are sometimes hard
• The TSP phase transition
• Complexity-theoretic models of phase transitions in search problems
• Problem structure heuristics and scaling behavior for genetic algorithms
• Restarts and exponential acceleration of the Davis-Putnam-Loveland-Logemann algorithm: A large deviation analysis of the generalized unit clause heuristic for random 3-SAT
• Constructing an asymptotic phase transition in random binary constraint satisfaction problems
• Constraint satisfaction -- algorithms and complexity analysis

This page was built for publication: The hardest constraint problems: A double phase transition

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