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

DOI10.1007/978-3-642-19754-3_17zbMATH Open1325.68109OpenAlexW2091872617MaRDI QIDQ2999343FDOQ2999343

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

kernellower boundsparameterized complexityupper boundshitting set

Mathematics Subject Classification ID

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

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)

• Hitting Set for hypergraphs of low VC-dimension
• 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
• Linear kernelizations for restricted 3-Hitting Set problems
• 3-hitting set on bounded degree hypergraphs: upper and lower bounds on the kernel size

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)