Solving CSP Instances Beyond the Phase Transition Using Stochastic Search Algorithms.
Luk SchoofsBart NaudtsPublished in: PPSN (2000)
Keyphrases
- phase transition
- random instances
- np complete problems
- stochastic search algorithms
- constraint satisfaction
- sat instances
- stochastic local search
- randomly generated
- graph coloring
- np complete
- sat problem
- constraint satisfaction problems
- satisfiability problem
- hard problems
- combinatorial problems
- random constraint satisfaction problems
- random sat
- constraint propagation
- lower bound
- average degree
- random graphs
- sat solvers
- pattern databases
- heuristic search
- hamiltonian cycle
- evaluation function
- sat encodings
- tabu search