Partially Polynomial Kernels for Set Cover and Test Cover

DOI10.4230/LIPICS.FSTTCS.2013.67MaRDI QIDQ2963898zbMATH OpenOpenAlexFDO

Authors Manu Basavaraju, Mathew C. Francis, M. S. Ramanujan, Saket Saurabh

Publication date 21 February 2017

Full work available at URL https://doi.org/10.4230/LIPIcs.FSTTCS.2013.67

zbMATH Keywords

set covertest coverkernelizationparameterized algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Nonnumerical algorithms (68W05)

Recommendations

• Partially polynomial kernels for set cover and test cover
• (Non-)existence of polynomial kernels for the test cover problem
• Polynomial kernels for vertex cover parameterized by small degree modulators
• Tight kernels for covering and hitting: point hyperplane cover and polynomial point hitting set
• A randomized polynomial kernelization for vertex cover with a smaller parameter
• A Randomized Polynomial Kernelization for Vertex Cover with a Smaller Parameter
• Polynomial kernels for \textsc{Dominating Set} in graphs of bounded degeneracy and beyond
• The set of parameterized k-covers problem
• A Class of Polynomially Solvable Set-Covering Problems
• Complexity and approximability of the cover polynomial

Cited in

(8)

• Partially polynomial kernels for set cover and test cover
• Parameterizations of test cover with bounded test sizes
• Parameterized study of the test cover problem
• (Non-)existence of polynomial kernels for the test cover problem
• Deterministic versus randomized adaptive test cover
• Hitting and covering partially
• Randomized adaptive test cover
• Combinatorial search in two and more rounds

This page was built for publication: Partially Polynomial Kernels for Set Cover and Test Cover

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2963898)