The Complexity of Some Polynomial Network Consistency Algorithms for Constraint Satisfaction Problems.
Alan K. MackworthEugene C. FreuderPublished in: Artif. Intell. (1985)
Keyphrases
- constraint satisfaction problems
- pseudo boolean optimization
- constraint problems
- path consistency
- constraint satisfaction
- computational problems
- constraint propagation
- constraint graph
- tractable subclasses
- combinatorial problems
- constraint optimization
- non binary
- decomposition methods
- constraint programming
- backtracking search
- arc consistency algorithm
- soft constraints
- constraint networks
- search space
- space complexity
- computational complexity
- global constraints
- orders of magnitude
- binary constraints
- constraint solvers
- np complete
- solving constraint satisfaction problems
- worst case
- arc consistency
- constraint solver
- forward checking
- planning problems
- backtracking algorithm
- simulated annealing
- finding optimal solutions