The Complexity of General-Valued Constraint Satisfaction Problems Seen from the Other Side.
Clément CarbonnelMiguel RomeroStanislav ZivnýPublished in: SIAM J. Comput. (2022)
Keyphrases
- constraint satisfaction problems
- constraint satisfaction
- constraint propagation
- constraint programming
- graph coloring problems
- np complete
- tractable subclasses
- tractable classes
- non binary
- combinatorial problems
- pseudo boolean optimization
- search space
- computational problems
- arc consistency
- special case
- global constraints
- sat problem
- solving constraint satisfaction problems
- np hard
- constraint problems
- constraint solving
- forward checking
- decomposition methods
- space complexity
- path consistency
- backtracking search
- soft constraints
- worst case
- computational complexity