The Tractability of CSP Classes Defined by Forbidden Patterns

DOI10.1613/jair.3651zbMath1253.68296OpenAlexW1615001418MaRDI QIDQ3143567

Dániel Marx, Martin C. Cooper, Páidí Creed, 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 complexityCSPconstraint satisfactiontractabilityforbidden patternconstraint pattern

Mathematics Subject Classification ID

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

Related Items (13)

Tractability in constraint satisfaction problems: a survey ⋮ Binary constraint satisfaction problems defined by excluded topological minors ⋮ On Singleton Arc Consistency for CSPs Defined by Monotone Patterns ⋮ CSP beyond tractable constraint languages ⋮ Hybrid Tractable Classes of Constraint Problems ⋮ Backdoor Sets for CSP. ⋮ The Broken-Triangle Property with Adjoint Values ⋮ On singleton arc consistency for CSPs defined by monotone patterns ⋮ Backdoors into heterogeneous classes of SAT and CSP ⋮ 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

Uses Software

• Algorithm 447

This page was built for publication: The Tractability of CSP Classes Defined by Forbidden Patterns