Generalizing constraint satisfaction on trees: hybrid tractability and variable elimination

DOI10.1016/J.ARTINT.2010.03.002zbMATH Open1205.68372OpenAlexW2136070841MaRDI QIDQ991007FDOQ991007

P. Jeavons, András Z. Salamon, M. 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 orderingvariable eliminationarc consistency

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Fundamental properties of neighbourhood substitution in constraint satisfaction problems
• The complexity of homomorphism and constraint satisfaction problems seen from the other side
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Complexity classifications of Boolean constraint satisfaction problems
• A dichotomy theorem for constraint satisfaction problems on a 3-element set
• A Sufficient Condition for Backtrack-Free Search
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• Classifying the Complexity of Constraints Using Finite Algebras
• The complexity of satisfiability problems
• Network-based heuristics for constraint-satisfaction problems
• On the algebraic structure of combinatorial problems
• Characterising tractable constraints
• Typed Guarded Decompositions for Constraint Satisfaction
• On the minimality and global consistency of row-convex constraint networks
• Constraint tightness and looseness versus local and global consistency
• The Structure of Tractable Constraint Satisfaction Problems
• Tractable constraints on ordered domains
• A unified theory of structural tractability for constraint satisfaction problems
• Tree clustering for constraint networks
• A sufficient condition for backtrack-bounded search
• Bucket elimination: A unifying framework for reasoning

Cited In (17)

• Broken triangles: from value merging to a tractable class of general-arity constraint satisfaction problems
• Hybrid Tractable Classes of Constraint Problems
• On a new extension of BTP for binary CSPs
• Tractability in constraint satisfaction problems: a survey
• On singleton arc consistency for CSPs defined by monotone patterns
• A hybrid tractable class for non-binary CSPs
• Hybrid tractability of valued constraint problems
• The Broken-Triangle Property with Adjoint Values
• Constraint satisfaction with bounded treewidth revisited
• A polynomial relational class of binary CSP
• Binary constraint satisfaction problems defined by excluded topological minors
• The power of propagation: when GAC is enough
• Characterising the complexity of constraint satisfaction problems defined by 2-constraint forbidden patterns
• Variable and value elimination in binary constraint satisfaction via forbidden patterns
• On Singleton Arc Consistency for CSPs Defined by Monotone Patterns
• Galois connections for patterns: an algebra of labelled graphs
• A new branch-and-filter exact algorithm for binary constraint satisfaction problems

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q991007)