The complexity of constraint satisfaction revisited

DOI10.1016/0004-3702(93)90170-GOpenAlexW2012694101MaRDI QIDQ2675271

Eugene C. Freuder, Alan K. Mackworth

Publication date: 21 September 2022

Published in: Artificial Intelligence (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0004-3702(93)90170-g

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) History of computer science (68-03)

Related Items

Automatic generation of dominance breaking nogoods for a class of constraint optimization problems, The complexity of soft constraint satisfaction, Combinatorial problems raised from 2-semilattices, Empirically-derived estimates of the complexity of labeling line drawings of polyhedral scenes, Using constraint metaknowledge to reduce arc consistency computation, Conjunctive-query containment and constraint satisfaction

Cites Work

• Unnamed Item
• Arc consistency for factorable relations.
• Network-based heuristics for constraint-satisfaction problems
• Tree clustering for constraint networks
• Consistency in networks of relations
• Networks of constraints: Fundamental properties and applications to picture processing
• REF-ARF: A system for solving problems stated as procedures
• On the parallel complexity of discrete relaxation in constraint satisfaction networks