Solving CSPs Using Weak Local Consistency
From MaRDI portal
Publication:5009788
DOI10.1137/18M117577XOpenAlexW3185454258MaRDI QIDQ5009788
Publication date: 6 August 2021
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/18m117577x
Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15) Descriptive complexity and finite models (68Q19)
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Mal'tsev conditions, lack of absorption, and solvability.
- Maltsev families of varieties closed under join or Maltsev product
- Bounded width problems and algebras
- Peek arc consistency
- A characterization of idempotent strong Mal'cev conditions for congruence meet-semidistributivity in locally finite varieties
- Theoretical analysis of singleton arc consistency and its extensions
- Majority constraints have bounded pathwidth duality
- Robustly Solvable Constraint Satisfaction Problems
- The collapse of the bounded width hierarchy
- Robust Satisfiability for CSPs
- Near Unanimity Constraints Have Bounded Pathwidth Duality
- Constraint Satisfaction Problems Solvable by Local Consistency Methods
- The structure of finite algebras
- The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
- Robust algorithms with polynomial loss for near-unanimity CSPs
- Weak consistency notions for all the CSPs of bounded width
- Arc consistency and friends
- Constraint Satisfaction Problems of Bounded Width
- Algebraic approach to promise constraint satisfaction
- Classifying the Complexity of Constraints Using Finite Algebras
- The complexity of satisfiability problems
- Robust satisfiability of constraint satisfaction problems
- Dualities for Constraint Satisfaction Problems
This page was built for publication: Solving CSPs Using Weak Local Consistency
