Generalizing constraint satisfaction on trees: hybrid tractability and variable elimination

DOI10.1016/J.ARTINT.2010.03.002MaRDI QIDQ991007zbMATH OpenOpenAlexFDO

Authors M. C. Cooper, P. Jeavons, András Z. Salamon

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)

Recommendations

• Broken triangles: from value merging to a tractable class of general-arity constraint satisfaction problems
• On a new extension of BTP for binary CSPs
• The Broken-Triangle Property with Adjoint Values
• Variable and value elimination in binary constraint satisfaction via forbidden patterns
• Tractable constraints on ordered domains

Cites work

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

Cited in

(19)

• Broken triangles: from value merging to a tractable class of general-arity constraint satisfaction problems
• Tractability in constraint satisfaction problems: a survey
• On a new extension of BTP for binary CSPs
• On singleton arc consistency for CSPs defined by monotone patterns
• A hybrid tractable class for non-binary CSPs
• On singleton arc consistency for CSPs defined by monotone patterns
• 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
• Hybrid tractable classes of constraint problems
• Galois connections for patterns: an algebra of labelled graphs
• On tree-preserving constraints
• A new branch-and-filter exact algorithm for binary constraint satisfaction problems
• Uncovering trees in constraint networks

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)