Constraint satisfaction -- algorithms and complexity analysis

DOI10.1016/0020-0190(95)00089-UMaRDI QIDQ672029zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• scientific article; zbMATH DE number 1234562
• Fast parallel constraint satisfaction
• Constraints, consistency and closure
• scientific article; zbMATH DE number 1094771
• Constraint satisfaction problems: Algorithms and applications

Cites work

• scientific article; zbMATH DE number 1194730 (Why is no real title available?)
• scientific article; zbMATH DE number 67483 (Why is no real title available?)
• scientific article; zbMATH DE number 194009 (Why is no real title available?)
• scientific article; zbMATH DE number 1149412 (Why is no real title available?)
• An exact algorithm for the constraint satisfaction problem: Application to logical inference
• An optimal k-consistency algorithm
• Characterising tractable constraints
• Constraint satisfaction from a deductive viewpoint
• Decomposing constraint satisfaction problems using database techniques
• Experimental evaluation of preprocessing algorithms for constraint satisfaction problems
• From local to global consistency
• Locating the phase transition in binary constraint satisfaction problems
• Minimizing conflicts: A heuristic repair method for constraint satisfaction and scheduling problems
• Parallel problem solving from nature -- PPSN III. International conference on evolutionary computation. The 3rd conference, Jerusalem, Israel, October 9--14, 1994. Proceedings
• Synthesizing constraint expressions
• The hardest constraint problems: A double phase transition
• Using constraint metaknowledge to reduce arc consistency computation

Cited in

(25)

• Complexity of Constraint Satisfaction Problems over Finite Subsets of Natural Numbers.
• Constraint updating
• Experimental complexity analysis of continuous constraint satisfaction problems.
• scientific article; zbMATH DE number 2096835 (Why is no real title available?)
• Revisiting global constraint satisfaction
• A synthesis of constraint satisfaction and constraint solving
• The complexity of constraint satisfaction revisited
• scientific article; zbMATH DE number 1322793 (Why is no real title available?)
• Constraint satisfaction from a deductive viewpoint
• Local consistency for extended CSPs
• A note on domination 3-edge-critical planar graphs
• On the complexity of trial and error for constraint satisfaction problems
• The complexity of reasoning with global constraints
• scientific article; zbMATH DE number 1696546 (Why is no real title available?)
• scientific article; zbMATH DE number 1708126 (Why is no real title available?)
• Constraint Satisfaction Parameterized by Solution Size
• Fine-grained conflict resolution in constraint satisfaction problems
• Recent Advances in Constraints
• Polynomial time termination and constraint satisfaction tests
• The logic of constraint satisfaction
• scientific article; zbMATH DE number 1822444 (Why is no real title available?)
• Constraint satisfaction problem with bilevel constraint: Application to interpretation of over-segmented images
• The complexity of constraint satisfaction problems for small relation algebras
• Solution techniques for constraint satisfaction problems: Advanced approaches
• Algorithms and Computation

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q672029)