The tractability of CSP classes defined by forbidden patterns

DOI10.1613/JAIR.3651MaRDI QIDQ3143567zbMATH OpenOpenAlexFDO

Authors M. C. Cooper, Páidí Creed, Dániel Marx, András Z. Salamon, David A. Cohen

Publication date 3 December 2012

Published in Journal of Artificial Intelligence Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1613/jair.3651

zbMATH Keywords

computational complexityconstraint patternconstraint satisfactionCSPforbidden patterntractability

Mathematics Subject Classification ID

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

Recommendations

• Characterising the complexity of constraint satisfaction problems defined by 2-constraint forbidden patterns
• The Power of Arc Consistency for CSPs Defined by Partially-Ordered Forbidden Patterns
• scientific article; zbMATH DE number 6825406
• Tractability in constraint satisfaction problems: a survey
• Binary constraint satisfaction problems defined by excluded topological minors

Cited in

(22)

• Implications of forbidden structures for extremal algorithmic problems
• Binary constraint satisfaction problems defined by excluded topological minors
• On singleton arc consistency for CSPs defined by monotone patterns
• Galois connections for patterns: an algebra of labelled graphs
• Characterising the complexity of constraint satisfaction problems defined by 2-constraint forbidden patterns
• Variable and value elimination in binary constraint satisfaction via forbidden patterns
• Broken triangles: from value merging to a tractable class of general-arity constraint satisfaction problems
• Tractability in constraint satisfaction problems: a survey
• On singleton arc consistency for CSPs defined by monotone patterns
• Bounded-Degree Forbidden Patterns Problems Are Constraint Satisfaction Problems
• Effectiveness of structural restrictions for hybrid CSPs
• Universal Structures and the Logic of Forbidden Patterns
• A unifying framework for structural properties of CSPS: definitions, complexity, tractability
• Universal Structures and the logic of Forbidden Patterns
• scientific article; zbMATH DE number 6825406 (Why is no real title available?)
• The Broken-Triangle Property with Adjoint Values
• The Power of Arc Consistency for CSPs Defined by Partially-Ordered Forbidden Patterns
• Hybrid tractable classes of constraint problems
• Backdoor sets for CSP
• CSP beyond tractable constraint languages
• Hybrid tractability of valued constraint problems
• Backdoors into heterogeneous classes of SAT and CSP

Describes a project that uses

Uses Software

• Algorithm 447

This page was built for publication: The tractability of CSP classes defined by forbidden patterns

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