Graph-Theoretic Concepts in Computer Science

DOI10.1007/11604686MaRDI QIDQ5897539zbMATH OpenFDO

Authors Georg Gottlob, Martin Grohe, Nysret Musliu, Marko Samer, Francesco Scarcello

Publication date 1 November 2006

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/11604686

Mathematics Subject Classification ID

Hypergraphs (05C65) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• scientific article; zbMATH DE number 1834638
• Hypertree decompositions and tractable queries
• A backtracking-based algorithm for hypertree decomposition
• Complexity Analysis of Generalized and Fractional Hypertree Decompositions
• Width functions for hypertree decompositions

Cited in

(29)

• It's all a matter of degree. Using degree information to optimize multiway joins
• Hyper-T-width and hyper-D-width: Stable connectivity measures for hypergraphs
• Efficiently enumerating minimal triangulations
• Hypertree width and related hypergraph invariants
• Approximating width parameters of hypergraphs with excluded minors
• Generalized hypertree decompositions: NP-hardness and tractable variants
• Beyond Hypertree Width: Decomposition Methods Without Decompositions
• Balanced queries: divide and conquer
• Tree projections and structural decomposition methods: minimality and game-theoretic characterization
• Minor-matching hypertree width
• Approximating fractional hypertree width
• Hypergraphs in Model Checking: Acyclicity and Hypertree-Width versus Clique-Width
• scientific article; zbMATH DE number 1834638 (Why is no real title available?)
• Optimizing answer set computation via heuristic-based decomposition
• Complexity Analysis of Generalized and Fractional Hypertree Decompositions
• Sum-of-Products with Default Values: Algorithms and Complexity Results
• Approximating acyclicity parameters of sparse hypergraphs
• A backtracking-based algorithm for hypertree decomposition
• Width functions for hypertree decompositions
• Uniform Constraint Satisfaction Problems and Database Theory
• Computing optimal hypertree decompositions with SAT
• Fast parallel hypertree decompositions in logarithmic recursion depth
• FPT approximation of generalised hypertree width for bounded intersection hypergraphs
• Hypertree decompositions and tractable queries
• Conjunctive queries with comparisons
• FPT approximation of generalised hypertree width for bounded intersection hypergraphs
• Constraint satisfaction with bounded treewidth revisited
• Weighted hypertree decompositions and optimal query plans
• An annotated bibliography on guaranteed graph searching

This page was built for publication: Graph-Theoretic Concepts in Computer Science

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