Universal algebra and hardness results for constraint satisfaction problems.
Benoît LarosePascal TessonPublished in: Theor. Comput. Sci. (2009)
Keyphrases
- constraint satisfaction problems
- np complete
- np hard
- constraint satisfaction
- random instances
- phase transition
- constraint propagation
- constraint programming
- search space
- combinatorial problems
- non binary
- relational algebra
- query language
- constraint networks
- computational complexity
- arc consistency
- worst case
- data model
- global constraints
- graph coloring
- pseudo boolean optimization
- finite domain
- constraint solving
- sat problem
- randomly generated
- forward checking
- constraint graph
- configuration problems
- constraint optimization
- solving constraint satisfaction problems
- backtracking algorithm
- finding optimal solutions
- lower bound