Computing hypergraph width measures exactly

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

zbMATH Keywords

design of algorithmsgraph algorithmsexact exponential algorithmsfractional hypertree-widthgeneralized hypertree-width

Mathematics Subject Classification ID

Trees (05C05) Applications of graph theory (05C90) Hypergraphs (05C65)

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?