On the Parallel Complexity of Discrete Relaxation in Constraint Satisfaction Networks.
Simon KasifPublished in: Artif. Intell. (1990)
Keyphrases
- constraint satisfaction
- constraint satisfaction problems
- heuristic search
- constraint propagation
- constraint relaxation
- constraint programming
- phase transition
- relaxation labeling
- arc consistency
- worst case
- constraint problems
- probabilistic reasoning
- computational complexity
- soft constraints
- objective function
- constrained problems
- product configuration
- russian doll search
- constraint solving
- space complexity
- network structure
- constraint networks
- sat solvers
- forward checking
- backtrack search
- backtracking algorithms
- search strategies
- max csp