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

DOI10.1007/978-3-642-19754-3_17MaRDI QIDQ2999343zbMATH OpenOpenAlexFDO

Authors Fenghui Zhang, Iyad Kanj

Publication date 12 May 2011

Published in Theory and Practice of Algorithms in (Computer) Systems (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-19754-3_17

zbMATH Keywords

hitting setkernellower boundsparameterized complexityupper bounds

Mathematics Subject Classification ID

Hypergraphs (05C65) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• 3-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
• A kernelization algorithm for \(d\)-hitting set

Cited in

(6)

• The Union of Minimal Hitting Sets: Parameterized Combinatorial Bounds and Counting
• Hitting Set for hypergraphs of low VC-dimension
• 3-hitting set on bounded degree hypergraphs: upper and lower bounds on the kernel size
• Parameterized and Exact Computation
• Kernels for below-upper-bound parameterizations of the hitting set and directed dominating set problems
• Linear kernelizations for restricted 3-Hitting Set problems

This page was built for publication: 3-\textsc{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 Q2999343)