The hardest constraint problems: A double phase transition
From MaRDI portal
Publication:1337687
DOI10.1016/0004-3702(94)90088-4zbMath0938.68826OpenAlexW2002627038MaRDI QIDQ1337687
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
Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)
Related Items
An improved upper bound on the non-3-colourability threshold, Asymptotic and finite size parameters for phase transitions: Hamiltonian circuit as a case study, Computation with Polynomial Equations and Inequalities Arising in Combinatorial Optimization, Easy problems are sometimes hard, Statistical regimes across constrainedness regions, The impact of search heuristics on heavy-tailed behaviour, Complexity of Coloring Random Graphs, Average-case complexity of backtrack search for coloring sparse random graphs, Phase transitions and the search problem, Experimental results on the crossover point in random 3-SAT, The satisfiability constraint gap, An empirical study of phase transitions in binary constraint satisfaction problems, Refining the phase transition in combinatorial search, Implicates and prime implicates in random 3-SAT, Critical behavior in the computational cost of satisfiability testing, Problem structure heuristics and scaling behavior for genetic algorithms, The TSP phase transition, Experimental complexity analysis of continuous constraint satisfaction problems., A Model to Study Phase Transition and Plateaus in Relational Learning, Constraint satisfaction -- algorithms and complexity analysis, Constructive generation of very hard 3-colorability instances, Towards a practical engineering tool for rostering, Accelerating backtrack search with a best-first-search strategy, 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, Complexity studies of a temporal constraint propagation algorithm: a statistical analysis, Frozen development in graph coloring, Constructing an asymptotic phase transition in random binary constraint satisfaction problems, A generative power-law search tree model, Empirically-derived estimates of the complexity of labeling line drawings of polyhedral scenes, Complexity-theoretic models of phase transitions in search problems
Cites Work
