Variable and value elimination in binary constraint satisfaction via forbidden patterns
From MaRDI portal
Publication:2353394
DOI10.1016/j.jcss.2015.02.001zbMath1320.68168arXiv1502.03796OpenAlexW2135836460MaRDI QIDQ2353394
Guillaume Escamocher, David A. Cohen, Stanislav Živný, Martin C. Cooper
Publication date: 13 July 2015
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1502.03796
Related Items
Binary constraint satisfaction problems defined by excluded topological minors ⋮ On Singleton Arc Consistency for CSPs Defined by Monotone Patterns ⋮ Hybrid Tractable Classes of Constraint Problems ⋮ The Broken-Triangle Property with Adjoint Values ⋮ On singleton arc consistency for CSPs defined by monotone patterns ⋮ On a new extension of BTP for binary CSPs ⋮ Broken triangles: from value merging to a tractable class of general-arity constraint satisfaction problems
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Broken triangles: from value merging to a tractable class of general-arity constraint satisfaction problems
- Principles and practice of constraint programming. 20th international conference, CP 2014, Lyon, France, September 8--12, 2014. Proceedings
- Generalizing constraint satisfaction on trees: hybrid tractability and variable elimination
- The ellipsoid method and its consequences in combinatorial optimization
- Fundamental properties of neighbourhood substitution in constraint satisfaction problems
- Boosting search with variable elimination in constraint optimization and constraint satisfaction problems
- Characterising the complexity of constraint satisfaction problems defined by 2-constraint forbidden patterns
- An optimal coarse-grained arc consistency algorithm
- Conflict-directed \(A^{*}\) and its role in model-based embedded systems
- Tractable Triangles and Cross-Free Convexity in Discrete Optimisation
- A weighted CSP approach to cost-optimal planning
- A Dichotomy Theorem for the General Minimum Cost Homomorphism Problem
- The Tractability of CSP Classes Defined by Forbidden Patterns
- Watched Literals for Constraint Propagation in Minion
- Some New Tractable Classes of CSPs and Their Relations with Backtracking Algorithms
- Consistency restoration and explanations in dynamic CSPs---Application to configuration
