Hyperconsistency width for constraint satisfaction: Algorithms and complexity results

DOI10.1007/978-3-642-02029-2_9MaRDI QIDQ3655143zbMATH OpenOpenAlexWikidataFDO

Authors Georg Gottlob, Gianluigi Greco, Bruno Marnette

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)

Recommendations

• Beyond Hypertree Width: Decomposition Methods Without Decompositions
• Tractable hypergraph properties for constraint satisfaction and conjunctive queries
• Tractable hypergraph properties for constraint satisfaction and conjunctive queries
• Computing hypergraph width measures exactly
• Approximating fractional hypertree width

Cites work

• A comparison of structural CSP decomposition methods
• Beyond Hypertree Width: Decomposition Methods Without Decompositions
• Boosting search with variable elimination in constraint optimization and constraint satisfaction problems
• Conjunctive-query containment and constraint satisfaction
• Decomposing constraint satisfaction problems using database techniques
• From local to global consistency
• Generalized hypertree decompositions: NP-hardness and tractable variants
• scientific article; zbMATH DE number 839556 (Why is no real title available?)
• Hypertree decompositions and tractable queries
• Hypertree-width and related hypergraph invariants
• Query evaluation via tree-decompositions
• The core of a graph
• Tree Projections: Hypergraph Games and Minimality

Cited in

(3)

• Generalized hypertree decomposition for solving non binary CSP with compressed table constraints
• Semantic acyclicity for conjunctive queries: approximations and constraints
• Sets with cardinality constraints in satisfiability modulo theories

This page was built for publication: Hyperconsistency width for constraint satisfaction: Algorithms and complexity results

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