On the power of structural decompositions of graph-based representations of constraint problems

DOI10.1016/j.artint.2009.12.004zbMath1207.68355OpenAlexW2064249627MaRDI QIDQ969532

Gianluigi Greco, Francesco Scarcello

Publication date: 7 May 2010

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

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

zbMATH Keywords

incidence graphstreewidthhypergraphsdecomposition methodsconstraint satisfactiondual graphsprimal graphs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Related Items (4)

Characteristic function games with restricted agent interactions: core-stability and coalition structures ⋮ On the complexity of core, kernel, and bargaining set ⋮ Tree projections and constraint optimization problems: fixed-parameter tractability and parallel algorithms ⋮ Greedy strategies and larger islands of tractability for conjunctive queries and constraint satisfaction problems

Cites Work

• Unnamed Item
• Unnamed Item
• Hypertree decompositions and tractable queries
• Constraint satisfaction with bounded treewidth revisited
• A unified theory of structural tractability for constraint satisfaction problems
• Decomposing constraint satisfaction problems using database techniques
• Conjunctive query containment revisited
• A comparison of structural CSP decomposition methods
• Conjunctive-query containment and constraint satisfaction
• Binary vs. non-binary constraints
• Syntactic Characterization of Tree Database Schemas
• Generalized hypertree decompositions: NP-hardness and tractable variants
• Constraint solving via fractional edge covers
• Graph minors. II. Algorithmic aspects of tree-width
• A sufficient condition for backtrack-bounded search
• Power of Natural Semijoins
• Uniform Constraint Satisfaction Problems and Database Theory
• Computing LOGCFL certificates

This page was built for publication: On the power of structural decompositions of graph-based representations of constraint problems