A note on max \(k\)-vertex cover: faster FPT-AS, smaller approximate kernel and improved approximation

DOI10.4230/OASICS.SOSA.2019.15zbMATH Open1547.68627MaRDI QIDQ6593570

Pasin Manurangsi

Publication date: 26 August 2024

zbMATH Keywords

approximation algorithmsfixed-parameter algorithmsapproximate kernelizationmaximum \(k\)-vertex coverminimum \(k\)-vertex cover

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Approximation algorithms (68W25) Parameterized complexity, tractability and kernelization (68Q27)

Related Items (5)

On MAX-SAT with cardinality constraint ⋮ Minimizing total completion time with machine-dependent priority lists ⋮ A note on robust subsets of transversal matroids ⋮ On MAX-SAT with cardinality constraint ⋮ Improved FPT approximation scheme and approximate kernel for biclique-free max \(k\)-weight SAT: greedy strikes back

This page was built for publication: A note on max \(k\)-vertex cover: faster FPT-AS, smaller approximate kernel and improved approximation

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