Measures of Intrinsic Hardness for Constraint Satisfaction Problem Instances.
George BoukeasConstantinos HalatsisVassilis ZissimopoulosPanagiotis StamatopoulosPublished in: SOFSEM (2004)
Keyphrases
- constraint satisfaction problems
- random instances
- constraint satisfaction
- np complete
- phase transition
- np hard
- finding optimal solutions
- backtrack search
- randomly generated
- pseudo boolean optimization
- constraint programming
- constraint propagation
- non binary
- combinatorial problems
- arc consistency
- tractable classes
- forward checking
- constraint solving
- search space
- np complete problems
- constraint networks
- partial constraint satisfaction
- heuristic search
- soft constraints
- sat problem
- lower bound
- global constraints
- finite domain
- decomposition methods
- satisfiability problem
- dynamic constraint satisfaction problems
- graph coloring
- temporal constraints