Constraint satisfaction -- algorithms and complexity analysis

DOI10.1016/0020-0190(95)00089-UzbMath1051.68545OpenAlexW2053738200MaRDI QIDQ672029

Walter Hower

Publication date: 27 February 1997

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(95)00089-u

zbMATH Keywords

Computational complexityConstraint satisfactionCombinatorial problemsAnalysis and design of algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05)

Related Items (3)

Revisiting global constraint satisfaction ⋮ Constraint updating ⋮ Fine-grained conflict resolution in constraint satisfaction problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Constraint satisfaction from a deductive viewpoint
• An optimal k-consistency algorithm
• From local to global consistency
• Minimizing conflicts: A heuristic repair method for constraint satisfaction and scheduling problems
• Using constraint metaknowledge to reduce arc consistency computation
• An exact algorithm for the constraint satisfaction problem: Application to logical inference
• Decomposing constraint satisfaction problems using database techniques
• Characterising tractable constraints
• Experimental evaluation of preprocessing algorithms for constraint satisfaction problems
• The hardest constraint problems: A double phase transition
• Parallel problem solving from nature -- PPSN III. International conference on evolutionary computation. The 3rd conference, Jerusalem, Israel, October 9--14, 1994. Proceedings
• Locating the phase transition in binary constraint satisfaction problems
• Synthesizing constraint expressions

This page was built for publication: Constraint satisfaction -- algorithms and complexity analysis