Solving CSP Instances Beyond the Phase Transition Using Stochastic Search Algorithms.

Luk Schoofs Bart Naudts

Published 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