Generalizing constraint satisfaction on trees: hybrid tractability and variable elimination

DOI10.1016/j.artint.2010.03.002zbMath1205.68372OpenAlexW2136070841MaRDI QIDQ991007

Peter G. Jeavons, András Z. Salamon, Martin C. Cooper

Publication date: 2 September 2010

Published in: Artificial Intelligence (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.artint.2010.03.002

zbMATH Keywords

computational complexityconstraint satisfactiontractabilityvariable eliminationvariable orderingarc consistency

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Related Items (16)

Tractability in constraint satisfaction problems: a survey ⋮ Binary constraint satisfaction problems defined by excluded topological minors ⋮ On Singleton Arc Consistency for CSPs Defined by Monotone Patterns ⋮ A hybrid tractable class for non-binary CSPs ⋮ The power of propagation: when GAC is enough ⋮ Hybrid tractability of valued constraint problems ⋮ Hybrid Tractable Classes of Constraint Problems ⋮ The Broken-Triangle Property with Adjoint Values ⋮ On singleton arc consistency for CSPs defined by monotone patterns ⋮ A polynomial relational class of binary CSP ⋮ Galois connections for patterns: an algebra of labelled graphs ⋮ A new branch-and-filter exact algorithm for binary constraint satisfaction problems ⋮ On a new extension of BTP for binary CSPs ⋮ 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

Cites Work

• Unnamed Item
• Unnamed Item
• A unified theory of structural tractability for constraint satisfaction problems
• Network-based heuristics for constraint-satisfaction problems
• Tree clustering for constraint networks
• On the algebraic structure of combinatorial problems
• Characterising tractable constraints
• Fundamental properties of neighbourhood substitution in constraint satisfaction problems
• Bucket elimination: A unifying framework for reasoning
• Complexity Classifications of Boolean Constraint Satisfaction Problems
• Typed Guarded Decompositions for Constraint Satisfaction
• A dichotomy theorem for constraint satisfaction problems on a 3-element set
• 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
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• On the minimality and global consistency of row-convex constraint networks
• Constraint tightness and looseness versus local and global consistency
• Classifying the Complexity of Constraints Using Finite Algebras
• The complexity of satisfiability problems
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• The Structure of Tractable Constraint Satisfaction Problems
• Tractable constraints on ordered domains

This page was built for publication: Generalizing constraint satisfaction on trees: hybrid tractability and variable elimination