3-hitting set on bounded degree hypergraphs: upper and lower bounds on the kernel size

DOI10.1142/S1793830915500111zbMATH Open1316.05091OpenAlexW2178503409MaRDI QIDQ5261045FDOQ5261045

Authors Fenghui Zhang, Iyad Kanj 

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

zbMATH Keywords

kernellower boundsparameterized complexityupper boundshitting set

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Hypergraphs (05C65) General topics in the theory of algorithms (68W01)

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

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 854567 (Why is no real title available?)
• A kernelization algorithm for \(d\)-hitting set
• A top-down approach to search-trees: Improved algorithmics for 3-hitting set
• An efficient fixed-parameter algorithm for 3-hitting set
• Faster computation of maximum independent set and parameterized vertex cover for graphs with maximum degree 3
• Fundamentals of parameterized complexity
• Improved lower bounds on k‐independence
• Improved upper bounds for vertex cover
• Kernelization -- preprocessing with a guarantee
• Labeled search trees and amortized analysis: Improved upper bounds for NP-hard problems
• Linear kernelizations for restricted 3-Hitting Set problems
• On problems without polynomial kernels
• Parametric Duality and Kernelization: Lower Bounds and Upper Bounds on Kernel Size
• Two edge modification problems without polynomial kernels
• Vertex cover: Further observations and further improvements

Cited in

(6)

• Kernels for below-upper-bound parameterizations of the hitting set and directed dominating set problems
• Parameterized and Exact Computation
• The union of minimal hitting sets: parameterized combinatorial bounds and counting
• 3-\textsc{hitting set} on bounded degree hypergraphs: upper and lower bounds on the kernel size
• The Union of Minimal Hitting Sets: Parameterized Combinatorial Bounds and Counting
• Linear kernelizations for restricted 3-Hitting Set problems

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)