3-Hitting set on bounded degree hypergraphs: Upper and lower bounds on the kernel size
From MaRDI portal
Publication:5261045
DOI10.1142/S1793830915500111zbMath1316.05091OpenAlexW2178503409MaRDI QIDQ5261045
Publication date: 1 July 2015
Published in: Discrete Mathematics, Algorithms and Applications (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1142/s1793830915500111
Analysis of algorithms (68W40) Hypergraphs (05C65) General topics in the theory of algorithms (68W01)
Cites Work
- Fundamentals of parameterized complexity
- Improved upper bounds for vertex cover
- Labeled search trees and amortized analysis: Improved upper bounds for NP-hard problems
- A top-down approach to search-trees: Improved algorithmics for 3-hitting set
- An efficient fixed-parameter algorithm for 3-hitting set
- A kernelization algorithm for \(d\)-hitting set
- Linear kernelizations for restricted 3-Hitting Set problems
- Faster computation of maximum independent set and parameterized vertex cover for graphs with maximum degree 3
- On problems without polynomial kernels
- Two edge modification problems without polynomial kernels
- Vertex Cover: Further Observations and Further Improvements
- Kernelization – Preprocessing with a Guarantee
- Parametric Duality and Kernelization: Lower Bounds and Upper Bounds on Kernel Size
- Improved lower bounds on k‐independence
- Unnamed Item
- Unnamed Item
This page was built for publication: 3-Hitting set on bounded degree hypergraphs: Upper and lower bounds on the kernel size