3-hitting set on bounded degree hypergraphs: upper and lower bounds on the kernel size
From MaRDI portal
Publication:5261045
DOI10.1142/S1793830915500111zbMATH Open1316.05091OpenAlexW2178503409MaRDI QIDQ5261045FDOQ5261045
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
Recommendations
- 3-\textsc{hitting set} on bounded degree hypergraphs: upper and lower bounds on the kernel size
- Linear kernelizations for restricted 3-Hitting Set problems
- Parameterized and Exact Computation
- Kernelization Algorithms for d-Hitting Set Problems
- Kernels for below-upper-bound parameterizations of the hitting set and directed dominating set problems
Analysis of algorithms (68W40) Hypergraphs (05C65) General topics in the theory of algorithms (68W01)
Cites Work
- Fundamentals of parameterized complexity
- Title not available (Why is that?)
- A top-down approach to search-trees: Improved algorithmics for 3-hitting set
- A kernelization algorithm for \(d\)-hitting set
- On problems without polynomial kernels
- Kernelization – Preprocessing with a Guarantee
- Improved lower bounds on k‐independence
- Title not available (Why is that?)
- Improved upper bounds for vertex cover
- Faster computation of maximum independent set and parameterized vertex cover for graphs with maximum degree 3
- Parametric Duality and Kernelization: Lower Bounds and Upper Bounds on Kernel Size
- Vertex cover: Further observations and further improvements
- Labeled search trees and amortized analysis: Improved upper bounds for NP-hard problems
- An efficient fixed-parameter algorithm for 3-hitting set
- Linear kernelizations for restricted 3-Hitting Set problems
- Two edge modification problems without polynomial kernels
Cited In (2)
This page was built for publication: 3-hitting set on bounded degree hypergraphs: upper and lower bounds on the kernel size
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5261045)
