Generalized hypertree decompositions: NP-hardness and tractable variants

DOI10.1145/1568318.1568320MaRDI QIDQ3452226zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Georg Gottlob, Zoltán Miklós, Thomas Schwentick

Publication date 11 November 2015

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/1568318.1568320

zbMATH Keywords

conjunctive queryacyclichypergraphNP-completehypertree decompositiontractabletree projection problem

Mathematics Subject Classification ID

Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Hypergraphs (05C65)

Recommendations

• Complexity Analysis of Generalized and Fractional Hypertree Decompositions
• Hypertree decompositions and tractable queries
• Beyond Hypertree Width: Decomposition Methods Without Decompositions
• scientific article; zbMATH DE number 1834638
• Graph-Theoretic Concepts in Computer Science

Cited in

(31)

• Fractional covers of hypergraphs with bounded multi-intersection
• Structural tractability of counting of solutions to conjunctive queries
• Covers of Query Results
• Hyper-T-width and hyper-D-width: Stable connectivity measures for hypergraphs
• Coalitional games induced by matching problems: complexity and islands of tractability for the Shapley value
• Finding optimal triangulations parameterized by edge clique cover
• On the power of structural decompositions of graph-based representations of constraint problems
• A more general theory of static approximations for conjunctive queries
• Tree projections and structural decomposition methods: minimality and game-theoretic characterization
• Finding compact scheme forests in nested normal form is NP-hard
• A more general theory of static approximations for conjunctive queries
• Hypertree decompositions and tractable queries
• Fast and parallel decomposition of constraint satisfaction problems
• Tree projections and constraint optimization problems: fixed-parameter tractability and parallel algorithms
• Tree projections: Game characterization and computational aspects
• scientific article; zbMATH DE number 1834638 (Why is no real title available?)
• scientific article; zbMATH DE number 7238987 (Why is no real title available?)
• Generation of polynomial-time algorithms for some optimization problems on tree-decomposable graphs
• HyperBench. A benchmark and tool for hypergraphs and empirical findings
• Complexity Analysis of Generalized and Fractional Hypertree Decompositions
• Fast parallel hypertree decompositions in logarithmic recursion depth
• Generalized hypertree decomposition for solving non binary CSP with compressed table constraints
• Greedy strategies and larger islands of tractability for conjunctive queries and constraint satisfaction problems
• Structural tractability of enumerating CSP solutions
• Connected graph searching
• An annotated bibliography on guaranteed graph searching
• The power of non-ground rules in Answer Set Programming
• Efficiently enumerating minimal triangulations
• Hyperconsistency width for constraint satisfaction: Algorithms and complexity results
• Beyond Hypertree Width: Decomposition Methods Without Decompositions
• The Power of Local Consistency in Conjunctive Queries and Constraint Satisfaction Problems

This page was built for publication: Generalized hypertree decompositions: NP-hardness and tractable variants

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