FPT approximation of generalised hypertree width for bounded intersection hypergraphs

DOI10.4230/LIPICS.STACS.2024.48MaRDI QIDQ6902673zbMATH OpenFDO

Authors Matthias Lanzinger, Igor Razgon

Publication date 10 November 2025

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.STACS.2024.48

zbMATH Keywords

approximation algorithmshypergraphsparameterized algorithmsgeneralized hypertree width

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• scientific article; zbMATH DE number 2243403 (Why is no real title available?)
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Approximating fractional hypertree width
• Complexity Analysis of Generalized and Fractional Hypertree Decompositions
• Constraint solving via fractional edge covers
• Decomposing combinatorial auctions and set packing problems
• Fast and parallel decomposition of constraint satisfaction problems
• Generalized hypertree decompositions: NP-hardness and tractable variants
• Graph minors. II. Algorithmic aspects of tree-width
• Graph-Theoretic Concepts in Computer Science
• HyperBench. A benchmark and tool for hypergraphs and empirical findings
• Hypertree width and related hypergraph invariants
• On the Parameterized Complexity of Approximating Dominating Set
• Parameterized algorithms
• Progressive algorithms for domination and independence
• Robbers, marshals, and guards: Game theoretic and logical characterizations of hypertree width.
• Solving Dominating Set in Larger Classes of Graphs: FPT Algorithms and Polynomial Kernels

This page was built for publication: FPT approximation of generalised hypertree width for bounded intersection hypergraphs

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