Partially Polynomial Kernels for Set Cover and Test Cover

DOI10.4230/LIPICS.FSTTCS.2013.67zbMATH Open1359.68286OpenAlexW2241221468MaRDI QIDQ2963898FDOQ2963898

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

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

zbMATH Keywords

set covertest coverkernelizationparameterized algorithms

Mathematics Subject Classification ID

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

Cited In (8)

• 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
• Partially polynomial kernels for set cover and test cover

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)