Generalizing constraint satisfaction on trees: hybrid tractability and variable elimination
type: Item
instance of: scholarly article
title: Generalizing constraint satisfaction on trees: hybrid tractability and variable elimination
zbMATH Open document ID: 1205.68372
author: M. C. Cooper
author: P. Jeavons
author: András Z. Salamon
published in: Artificial Intelligence
publication date: 2010-09-02T00:00:00Z
Mathematics Subject Classification ID: 68T20
zbMATH DE Number: 5777561
zbMATH Keywords: constraint satisfaction
zbMATH Keywords: tractability
zbMATH Keywords: computational complexity
zbMATH Keywords: arc consistency
zbMATH Keywords: variable ordering
zbMATH Keywords: variable elimination
MaRDI profile type: Publication
full work available at URL: j.artint.2010.03.002
OpenAlex ID: W2136070841
cites work: A Sufficient Condition for Backtrack-Free Search
cites work: Network-based heuristics for constraint-satisfaction problems
cites work: Classifying the Complexity of Constraints Using Finite Algebras
cites work: The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
cites work: A unified theory of structural tractability for constraint satisfaction problems
cites work: On the algebraic structure of combinatorial problems
cites work: The complexity of satisfiability problems
cites work: A dichotomy theorem for constraint satisfaction problems on a 3-element set
cites work: The Structure of Tractable Constraint Satisfaction Problems
cites work: The complexity of homomorphism and constraint satisfaction problems seen from the other side
cites work: Typed Guarded Decompositions for Constraint Satisfaction
cites work: A sufficient condition for backtrack-bounded search
cites work: A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
cites work: Constraint tightness and looseness versus local and global consistency
cites work: Fundamental properties of neighbourhood substitution in constraint satisfaction problems
cites work: Characterising tractable constraints
cites work: Q3184605
cites work: Tractable constraints on ordered domains
cites work: Tree clustering for constraint networks
cites work: On the minimality and global consistency of row-convex constraint networks
cites work: Bucket elimination: A unifying framework for reasoning
cites work: Q4475662
cites work: Complexity classifications of Boolean constraint satisfaction problems
DOI: 10.1016/J.ARTINT.2010.03.002
description: scientific article; zbMATH DE number 5777561