The Tractability of CSP Classes Defined by Forbidden Patterns
From MaRDI portal
Publication:3143567
DOI10.1613/jair.3651zbMath1253.68296MaRDI 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
computational complexity; CSP; constraint satisfaction; tractability; forbidden pattern; constraint pattern
68Q25: Analysis of algorithms and problem complexity
68T20: Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
Related Items
The Broken-Triangle Property with Adjoint Values, Hybrid Tractable Classes of Constraint Problems, Backdoor Sets for CSP., Broken triangles: from value merging to a tractable class of general-arity constraint satisfaction problems, Tractability in constraint satisfaction problems: a survey, Backdoors into heterogeneous classes of SAT and CSP, 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, On Singleton Arc Consistency for CSPs Defined by Monotone Patterns
Uses Software
