HyperConsistency Width for Constraint Satisfaction: Algorithms and Complexity Results

DOI10.1007/978-3-642-02029-2_9zbMath1194.68126OpenAlexW1598103905WikidataQ59259599 ScholiaQ59259599MaRDI QIDQ3655143

Georg Gottlob, Bruno Marnette, Gianluigi Greco

Publication date: 7 January 2010

Published in: Graph Theory, Computational Intelligence and Thought (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-02029-2_9

Mathematics Subject Classification ID

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

Related Items

Sets with Cardinality Constraints in Satisfiability Modulo Theories ⋮ Semantic Acyclicity for Conjunctive Queries: Approximations and Constraints

Cites Work

• Unnamed Item
• Unnamed Item
• The core of a graph
• Hypertree decompositions and tractable queries
• From local to global consistency
• Decomposing constraint satisfaction problems using database techniques
• Boosting search with variable elimination in constraint optimization and constraint satisfaction problems
• A comparison of structural CSP decomposition methods
• Conjunctive-query containment and constraint satisfaction
• Generalized hypertree decompositions: NP-hardness and tractable variants
• Query evaluation via tree-decompositions
• Tree Projections: Hypergraph Games and Minimality
• Beyond Hypertree Width: Decomposition Methods Without Decompositions