Compressing Bounded Degree Graphs

Autor: Pål Grønås Drange, R. B. Sandeep, Markus Sortland Dregi
Rok vydání: 2016
Předmět:
Zdroj: LATIN 2016: Theoretical Informatics ISBN: 9783662495285
LATIN
DOI: 10.1007/978-3-662-49529-2_27
Popis: Recently, Aravind et al. (IPEC 2014) showed that for any finite set of connected graphs \(\mathcal {H}\), the problem \(\mathcal {H}\)-Free Edge Deletion admits a polynomial kernelization on bounded degree input graphs. We generalize this theorem by no longer requiring the graphs in \(\mathcal {H}\) to be connected. Furthermore, we complement this result by showing that also \(\mathcal {H}\)-Free Edge Editing admits a polynomial kernelization on bounded degree input graphs.
Databáze: OpenAIRE
Popis
Abstrakt:Recently, Aravind et al. (IPEC 2014) showed that for any finite set of connected graphs \(\mathcal {H}\), the problem \(\mathcal {H}\)-Free Edge Deletion admits a polynomial kernelization on bounded degree input graphs. We generalize this theorem by no longer requiring the graphs in \(\mathcal {H}\) to be connected. Furthermore, we complement this result by showing that also \(\mathcal {H}\)-Free Edge Editing admits a polynomial kernelization on bounded degree input graphs.
ISBN:9783662495285
DOI:10.1007/978-3-662-49529-2_27