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: |
|