Generalized hypertree decompositions: NP-hardness and tractable variants
DOI10.1145/1568318.1568320zbMATH Open1325.68097DBLPjournals/jacm/GottlobMS09OpenAlexW2065023965WikidataQ59259597 ScholiaQ59259597MaRDI QIDQ3452226FDOQ3452226
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
Recommendations
conjunctive queryacyclichypergraphNP-completehypertree decompositiontractabletree projection problem
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)
Cited In (32)
- Tree projections and structural decomposition methods: minimality and game-theoretic characterization
- Structural tractability of counting of solutions to conjunctive queries
- Fractional covers of hypergraphs with bounded multi-intersection
- The power of non-ground rules in Answer Set Programming
- An annotated bibliography on guaranteed graph searching
- Hypertree decompositions and tractable queries
- Covers of Query Results
- Hyperconsistency width for constraint satisfaction: Algorithms and complexity results
- Greedy strategies and larger islands of tractability for conjunctive queries and constraint satisfaction problems
- Myhill-Nerode Methods for Hypergraphs
- Connected graph searching
- Title not available (Why is that?)
- Generalized hypertree decomposition for solving non binary CSP with compressed table constraints
- Hyper-T-width and hyper-D-width: Stable connectivity measures for hypergraphs
- Finding optimal triangulations parameterized by edge clique cover
- The Power of Local Consistency in Conjunctive Queries and Constraint Satisfaction Problems
- Finding compact scheme forests in nested normal form is NP-hard
- Structural tractability of enumerating CSP solutions
- Tree projections and constraint optimization problems: fixed-parameter tractability and parallel algorithms
- Efficiently enumerating minimal triangulations
- A more general theory of static approximations for conjunctive queries
- A more general theory of static approximations for conjunctive queries
- Title not available (Why is that?)
- Coalitional games induced by matching problems: complexity and islands of tractability for the Shapley value
- Generation of polynomial-time algorithms for some optimization problems on tree-decomposable graphs
- Complexity Analysis of Generalized and Fractional Hypertree Decompositions
- HyperBench. A benchmark and tool for hypergraphs and empirical findings
- Beyond Hypertree Width: Decomposition Methods Without Decompositions
- On the power of structural decompositions of graph-based representations of constraint problems
- Tree projections: Game characterization and computational aspects
- Fast parallel hypertree decompositions in logarithmic recursion depth
- Fast and parallel decomposition of 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)
