On approximate preprocessing for domination and hitting subgraphs with connected deletion sets

In this paper, we study the Connected H -hitting Set and Dominating Set problems from the perspective of approximate kernelization, a framework recently introduced by Lokshtanov et al. [STOC 2017]. For the Connected H -hitting set problem, we obtain an α-approximate kernel for every α > 1 and com...

Full description

Bibliographic Details
Published in:Journal of computer and system sciences : JCSS, Vol. 105 (2019), p. 158-170
Main Author: Eiben, Eduard
Other Involved Persons: Hermelin, Danny ; Ramanujan, M.S.
Format: electronic Article
Physical Description:Online-Ressource
QR Code: Show QR Code