Hybrid tractable classes of constraint problems
From MaRDI portal
Publication:4993597
DOI10.4230/DFU.VOL7.15301.113zbMATH Open1482.68107OpenAlexW2592770497MaRDI QIDQ4993597FDOQ4993597
Authors: M. C. Cooper, S. Zivny 
Publication date: 15 June 2021
Full work available at URL: https://hal.archives-ouvertes.fr/hal-03120300
Recommendations
Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Combinatorial optimization (90C27)
Cites Work
- Discrete Convex Analysis
- Characterising the complexity of constraint satisfaction problems defined by 2-constraint forbidden patterns
- Variable and value elimination in binary constraint satisfaction via forbidden patterns
- Broken triangles: from value merging to a tractable class of general-arity constraint satisfaction problems
- Tractable triangles and cross-free convexity in discrete optimisation
- The tractability of CSP classes defined by forbidden patterns
- The complexity of homomorphism and constraint satisfaction problems seen from the other side
- Graph minors. XX: Wagner's conjecture
- A hybrid tractable class for non-binary CSPs
- Generalizing constraint satisfaction on trees: hybrid tractability and variable elimination
- The ellipsoid method and its consequences in combinatorial optimization
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- A Sufficient Condition for Backtrack-Free Search
- Classifying the Complexity of Constraints Using Finite Algebras
- The strong perfect graph theorem
- From local to global consistency
- Characterising tractable constraints
- Domain permutation reduction for constraint satisfaction problems
- Recognizing Berge graphs
- Constraint Satisfaction Problems Solvable by Local Consistency Methods
- Constraint tightness and looseness versus local and global consistency
- Title not available (Why is that?)
- Colouring, constraint satisfaction, and complexity
- Tractability and learnability arising from algebras with few subpowers
- The complexity of conservative valued CSPs
- An algebraic theory of complexity for discrete optimization.
- Tractable constraints on ordered domains
- Hybrid tractability of valued constraint problems
- Boosting search with variable elimination in constraint optimization and constraint satisfaction problems
- On global warming: Flow-based soft global constraints
- A sufficient condition for backtrack-bounded search
- Mathematical Foundations of Computer Science 2003
- Fanout limitations on constraint systems
- Title not available (Why is that?)
- The power of linear programming for general-valued CSPs
- Symmetry definitions for constraint satisfaction problems
- Some new tractable classes of CSPs and their relations with backtracking algorithms
- The Power of Arc Consistency for CSPs Defined by Partially-Ordered Forbidden Patterns
- On Planar Boolean CSP
- Effectiveness of structural restrictions for hybrid CSPs
- Even delta-matroids and the complexity of planar Boolean CSPs
- On Planar Valued CSPs
Cited In (12)
- Beyond JWP: a tractable class of binary VCSPs via M-convex intersection
- Tractability in constraint satisfaction problems: a survey
- A hybrid tractable class for non-binary CSPs
- Hybrid tractability of valued constraint problems
- A tractable class of binary VCSPs via M-convex intersection
- PTAS for Sparse General-valued CSPs
- Effectiveness of structural restrictions for hybrid CSPs
- Galois connections for patterns: an algebra of labelled graphs
- The complexity of valued CSPs
- Hybrid VCSPs with crisp and valued conservative templates
- Tractable Optimization Problems through Hypergraph-Based Structural Restrictions
- Heterogeneous constraint solving
This page was built for publication: Hybrid tractable classes of constraint problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4993597)
