Hybrid tractable classes of constraint problems
type: Item
instance of: scholarly article
zbMATH Open document ID: 1482.68107
author: M. C. Cooper
author: S. Zivny
publication date: 2021-06-15T00:00:00Z
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68R05
Mathematics Subject Classification ID: 90C27
zbMATH DE Number: 7359809
zbMATH Keywords: constraint satisfaction problems
zbMATH Keywords: optimisation
zbMATH Keywords: tractability
MaRDI profile type: MaRDI publication profile
cites work: Constraint Satisfaction Problems Solvable by Local Consistency Methods
cites work: Classifying the Complexity of Constraints Using Finite Algebras
cites work: Recognizing Berge graphs
cites work: The strong perfect graph theorem
cites work: An algebraic theory of complexity for discrete optimization.
cites work: The tractability of CSP classes defined by forbidden patterns
cites work: Variable and value elimination in binary constraint satisfaction via forbidden patterns
cites work: Symmetry definitions for constraint satisfaction problems
cites work: Characterising tractable constraints
cites work: Broken triangles: from value merging to a tractable class of general-arity constraint satisfaction problems
cites work: Characterising the complexity of constraint satisfaction problems defined by 2-constraint forbidden patterns
cites work: Generalizing constraint satisfaction on trees: hybrid tractability and variable elimination
cites work: Hybrid tractability of valued constraint problems
cites work: Tractable triangles and cross-free convexity in discrete optimisation
cites work: The Power of Arc Consistency for CSPs Defined by Partially-Ordered Forbidden Patterns
cites work: Mathematical Foundations of Computer Science 2003
cites work: Q4386933
cites work: From local to global consistency
cites work: Boosting search with variable elimination in constraint optimization and constraint satisfaction problems
cites work: Q3586724
cites work: On Planar Boolean CSP
cites work: Fanout limitations on constraint systems
cites work: A Sufficient Condition for Backtrack-Free Search
cites work: A sufficient condition for backtrack-bounded search
cites work: On Planar Valued CSPs
cites work: Domain permutation reduction for constraint satisfaction problems
cites work: The complexity of homomorphism and constraint satisfaction problems seen from the other side
cites work: The ellipsoid method and its consequences in combinatorial optimization
cites work: Colouring, constraint satisfaction, and complexity
cites work: Tractability and learnability arising from algebras with few subpowers
cites work: Tractable constraints on ordered domains
cites work: Even delta-matroids and the complexity of planar Boolean CSPs
cites work: Effectiveness of structural restrictions for hybrid CSPs
cites work: The power of linear programming for general-valued CSPs
cites work: The complexity of conservative valued CSPs
cites work: Some new tractable classes of CSPs and their relations with backtracking algorithms
cites work: A hybrid tractable class for non-binary CSPs
cites work: Discrete Convex Analysis
cites work: Graph minors. XX: Wagner's conjecture
cites work: Combinatorial optimization. Polyhedra and efficiency (3 volumes)
cites work: Constraint tightness and looseness versus local and global consistency
cites work: On global warming: Flow-based soft global constraints
full work available at URL: hal-03120300
OpenAlex ID: W2592770497
title: Hybrid Tractable Classes of Constraint Problems
DOI: 10.4230/DFU.VOL7.15301.113
Recommended article: Hybrid tractability of valued constraint problems
Recommended article: Tractability in constraint satisfaction problems: a survey
Recommended article: The complexity of valued constraint satisfaction
Recommended article: The complexity of valued CSPs
Recommended article: Hybrid VCSPs with crisp and valued conservative templates
description: scientific article; zbMATH DE number 7359809