3-Hitting set on bounded degree hypergraphs: Upper and lower bounds on the kernel size

DOI10.1142/S1793830915500111zbMath1316.05091OpenAlexW2178503409MaRDI QIDQ5261045

Fenghui Zhang, Iyad A. 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

upper boundslower boundskernelparameterized complexityhitting set

Mathematics Subject Classification ID

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