Compressing Bounded Degree Graphs
Autor: | Pål Grønås Drange, R. B. Sandeep, Markus Sortland Dregi |
---|---|
Rok vydání: | 2016 |
Předmět: |
Polynomial (hyperelastic model)
Degree (graph theory) 0102 computer and information sciences 02 engineering and technology 01 natural sciences Combinatorics Indifference graph 010201 computation theory & mathematics Chordal graph Kernelization Bounded function 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing Connectivity Mathematics Complement (set theory) |
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 |
Externí odkaz: |
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 |