Refining the phase transition in combinatorial search
From MaRDI portal
Publication:2674181
DOI10.1016/0004-3702(95)00050-XMaRDI QIDQ2674181
Publication date: 22 September 2022
Published in: Artificial Intelligence (Search for Journal in Brave)
Coloring of graphs and hypergraphs (05C15) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)
Related Items
Dual mean field search for large scale linear and quadratic knapsack problems, Complexity of Coloring Random Graphs, Dual mean field annealing scheme for binary optimization under linear constraints, Average-case complexity of backtrack search for coloring sparse random graphs, Compiling constraint satisfaction problems, On market-inspired approaches to propositional satisfiability
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Optimization by Simulated Annealing
- Minimizing conflicts: A heuristic repair method for constraint satisfaction and scheduling problems
- Forward reasoning and dependency-directed backtracking in a system for computer-aided circuit analysis
- The hardest constraint problems: A double phase transition
- Exploiting the deep structure of constraint problems
- Easy problems are sometimes hard
- An empirical study of phase transitions in binary constraint satisfaction problems
- The solution of some random NP-hard problems in polynomial expected time
- Almost all k-colorable graphs are easy to color
- Optimization by Simulated Annealing: An Experimental Evaluation; Part II, Graph Coloring and Number Partitioning
- Heuristic Sampling: A Method for Predicting the Performance of Tree Searching Programs
- A Parallel Graph Coloring Heuristic
- A technique for colouring a graph applicable to large scale timetabling problems
