Tractable decision for a constraint language implies tractable search

DOI10.1023/B:CONS.0000036045.82829.94MaRDI QIDQ1768749zbMATH OpenOpenAlexFDO

Authors David A. Cohen

Publication date 15 March 2005

Published in Constraints (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1023/b:cons.0000036045.82829.94

zbMATH Keywords

complexitytractability

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Recommendations

• Tractability in constraint satisfaction problems: a survey
• Tractability by approximating constraint languages
• scientific article; zbMATH DE number 1008453
• Characterising tractable constraints
• Asking the Metaquestions in Constraint Tractability

Cited in

(6)

• The power of propagation: when GAC is enough
• Structural tractability of enumerating CSP solutions
• Domain permutation reduction for constraint satisfaction problems
• Enumerating all solutions of a Boolean CSP by non-decreasing weight
• CLAP: A New Algorithm for Promise CSPs
• Tractability by approximating constraint languages

This page was built for publication: Tractable decision for a constraint language implies tractable search

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