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

DOI10.1145/2933575.2933587MaRDI QIDQ4635926zbMATH OpenOpenAlexFDO

Authors M. C. Cooper, S. Zivny

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

arc consistencyconstraint satisfaction problemforbidden patterntractability

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 6825406
• A new class of binary CSPs for which arc-consistency is a decision procedure
• The tractability of CSP classes defined by forbidden patterns
• Bounds arc consistency for weighted CSPs
• Methods and Applications of Artificial Intelligence
• scientific article; zbMATH DE number 67482
• A fine-grained arc-consistency algorithm for non-normalized constraint satisfaction problems
• On singleton arc consistency for CSPs defined by monotone patterns
• On singleton arc consistency for CSPs defined by monotone patterns

Cited in

(10)

• The power of propagation: when GAC is enough
• On singleton arc consistency for CSPs defined by monotone patterns
• Galois connections for patterns: an algebra of labelled graphs
• On a new extension of BTP for binary CSPs
• Characterising the complexity of constraint satisfaction problems defined by 2-constraint forbidden patterns
• The tractability of CSP classes defined by forbidden patterns
• On singleton arc consistency for CSPs defined by monotone patterns
• scientific article; zbMATH DE number 6825406 (Why is no real title available?)
• Hybrid tractable classes of constraint problems
• Activity propagation in systems of linear inequalities and its relation to block-coordinate descent in linear programs

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

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