Hybrid Tractable Classes of Constraint Problems

DOI10.4230/DFU.Vol7.15301.113zbMath1482.68107OpenAlexW2592770497MaRDI QIDQ4993597

Publication date: 15 June 2021

Full work available at URL: https://hal.archives-ouvertes.fr/hal-03120300

optimisation constraint satisfaction problems tractability

Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Combinatorial optimization (90C27)

Related Items (5)

Beyond JWP: A Tractable Class of Binary VCSPs via M-Convex Intersection. ⋮ PTAS for Sparse General-valued CSPs ⋮ The Complexity of Valued CSPs ⋮ Galois connections for patterns: an algebra of labelled graphs ⋮ A Tractable Class of Binary VCSPs via M-Convex Intersection

Cites Work

Unnamed Item
Unnamed Item
Broken triangles: from value merging to a tractable class of general-arity constraint satisfaction problems
Colouring, constraint satisfaction, and complexity
Hybrid tractability of valued constraint problems
Graph minors. XX: Wagner's conjecture
Symmetry definitions for constraint satisfaction problems
The strong perfect graph theorem
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
From local to global consistency
Characterising tractable constraints
Boosting search with variable elimination in constraint optimization and constraint satisfaction problems
Combinatorial optimization. Polyhedra and efficiency (3 volumes)
Characterising the complexity of constraint satisfaction problems defined by 2-constraint forbidden patterns
Variable and value elimination in binary constraint satisfaction via forbidden patterns
Domain permutation reduction for constraint satisfaction problems
Recognizing Berge graphs
On global warming: Flow-based soft global constraints
Tractable Triangles and Cross-Free Convexity in Discrete Optimisation
The Tractability of CSP Classes Defined by Forbidden Patterns
The Complexity of Finite-Valued CSPs
Constraint Satisfaction Problems Solvable by Local Consistency Methods
On Planar Boolean CSP
Effectiveness of Structural Restrictions for Hybrid CSPs
The complexity of homomorphism and constraint satisfaction problems seen from the other side
A sufficient condition for backtrack-bounded search
A Sufficient Condition for Backtrack-Free Search
Constraint tightness and looseness versus local and global consistency
Discrete Convex Analysis
Even Delta-Matroids and the Complexity of Planar Boolean CSPs
On Planar Valued CSPs
The Power of Arc Consistency for CSPs Defined by Partially-Ordered Forbidden Patterns
Some New Tractable Classes of CSPs and Their Relations with Backtracking Algorithms
The Power of Linear Programming for General-Valued CSPs
Classifying the Complexity of Constraints Using Finite Algebras
Tractability and Learnability Arising from Algebras with Few Subpowers
The complexity of conservative valued CSPs
An Algebraic Theory of Complexity for Discrete Optimization
Mathematical Foundations of Computer Science 2003
Tractable constraints on ordered domains
Fanout limitations on constraint systems

This page was built for publication: Hybrid Tractable Classes of Constraint Problems