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
Language:English
ISSN:1090-2724
Physical Description:Online-Ressource
DOI:10.1016/j.jcss.2019.05.001
QR Code: Show QR Code