The Power of Arc Consistency for CSPs Defined by Partially-Ordered Forbidden Patterns

DOI10.1145/2933575.2933587zbMath1387.68118OpenAlexW2344102614MaRDI QIDQ4635926

Stanislav Živný, Martin C. Cooper

Publication date: 23 April 2018

Published in: Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science (Search for Journal in Brave)

Full work available at URL: https://oatao.univ-toulouse.fr/18764/1/cooper_18764.pdf

zbMATH Keywords

constraint satisfaction problemtractabilityforbidden patternarc consistency

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (5)

On Singleton Arc Consistency for CSPs Defined by Monotone Patterns ⋮ Activity propagation in systems of linear inequalities and its relation to block-coordinate descent in linear programs ⋮ The power of propagation: when GAC is enough ⋮ Hybrid Tractable Classes of Constraint Problems ⋮ On a new extension of BTP for binary CSPs

This page was built for publication: The Power of Arc Consistency for CSPs Defined by Partially-Ordered Forbidden Patterns