Computing hypergraph width measures exactly
From MaRDI portal
Publication:437685
DOI10.1016/j.ipl.2011.12.002zbMath1242.05058arXiv1106.4719OpenAlexW1979091081MaRDI QIDQ437685
Marc Thurley, Lukas Moll, Siamak Tazari
Publication date: 18 July 2012
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1106.4719
design of algorithmsgraph algorithmsexact exponential algorithmsfractional hypertree-widthgeneralized hypertree-width
Related Items
Finding optimal triangulations parameterized by edge clique cover ⋮ HyperBench ⋮ Unnamed Item ⋮ A revisit of the scheme for computing treewidth and minimum fill-in ⋮ Solving Graph Problems via Potential Maximal Cliques
Cites Work
- Hypertree decompositions and tractable queries
- On treewidth and minimum fill-in of asteroidal triple-free graphs
- Treewidth and Minimum Fill-in: Grouping the Minimal Separators
- Tractable hypergraph properties for constraint satisfaction and conjunctive queries
- Finding Induced Subgraphs via Minimal Triangulations
- Treewidth Computation and Extremal Combinatorics
- The complexity of homomorphism and constraint satisfaction problems seen from the other side
- Set Partitioning via Inclusion-Exclusion
- Constraint solving via fractional edge covers
- Exact Algorithms for Treewidth and Minimum Fill-In
- The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
- When is the evaluation of conjunctive queries tractable?
