Kernelization Using Structural Parameters on Sparse Graph Classes (2013)výskyt výsledku
| Identifikační kód | RIV/00216224:14330/13:00066378 |
|---|---|
| Název v anglickém jazyce | Kernelization Using Structural Parameters on Sparse Graph Classes |
| Druh | D - Článek ve sborníku |
| Jazyk | eng - angličtina |
| Obor - skupina | I - Informatika |
| Obor | IN - Informatika |
| Rok uplatnění | 2013 |
| Kód důvěrnosti údajů | S - Úplné a pravdivé údaje o výsledku nepodléhající ochraně podle zvláštních právních předpisů. |
| Počet výskytů výsledku | 2 |
| Počet tvůrců celkem | 8 |
| Počet domácích tvůrců | 4 |
| Výčet všech uvedených jednotlivých tvůrců | Jakub Gajarský (státní příslušnost: SK - Slovenská republika, domácí tvůrce: A, vedidk: 9663207) Petr Hliněný (státní příslušnost: CZ - Česká republika, domácí tvůrce: A, vedidk: 7595646) Jan Obdržálek (státní příslušnost: CZ - Česká republika, domácí tvůrce: A, vedidk: 3294099) Sebastian Ordyniak (státní příslušnost: DE - Spolková republika Německo, domácí tvůrce: A) Felix Reidl (státní příslušnost: DE - Spolková republika Německo) Peter Rossmanith (státní příslušnost: DE - Spolková republika Německo) Fernando Sanchez Villaamil (státní příslušnost: ES - Španělské království) Somnath Sikdar (státní příslušnost: IN - Indická republika) |
| Popis výsledku v anglickém jazyce | Meta-theorems for polynomial (linear) kernels have been the subject of intensive research in parameterized complexity. Heretofore, there were meta-theorems for linear kernels on graphs of bounded genus, H-minor-free graphs, and H-topological-minor-free graphs. To the best of our knowledge, there are no known meta-theorems for kernels for any of the larger sparse graph classes: graphs of bounded expansion, locally bounded expansion, and nowhere dense graphs. In this paper we prove meta-theorems for thesethree graph classes. More specifically, we show that graph problems that have finite integer index (FII) admit linear kernels on hereditary graphs of bounded expansion when parameterized by the size of a modulator to constant-treedepth graphs. For hereditary graph classes of locally bounded expansion, our result yields a quadratic kernel and for hereditary nowhere dense graphs, a polynomial kernel. |
| Klíčová slova oddělená středníkem | kernelization; parameterized complexity; sparse graphs |
| Stránka www, na které se nachází výsledek | - |
| DOI výsledku | 10.1007/978-3-642-40450-4_45 |
Údaje o výsledku v závislosti na druhu výsledku
| Název sborníku | ESA 2013 |
|---|---|
| ISBN | 9783642404498 |
| ISSN | 0302-9743 |
| Počet stran výsledku | 12 |
| Strana od-do | 529-540 |
| Název nakladatele | Springer |
| Místo vydání | Berlin Heidelberg |
| Místo konání akce | Sophia Antipolis, France |
| Datum konání akce | 2013 |
| Typ akce podle státní příslušnosti účastníků | WRD - Celosvětová |
| Kód UT WoS článku podle Web of Science | - |
Ostatní informace o výsledku
| Předkladatel | Masarykova univerzita / Fakulta informatiky |
|---|---|
| Dodavatel | MSM - Ministerstvo školství, mládeže a tělovýchovy (MŠMT) |
| Rok sběru | 2014 |
| Specifikace | RIV/00216224:14330/13:00066378!RIV14-MSM-14330___ |
| Datum poslední aktualizace výsledku | 29.05.2014 |
| Kontrolní číslo | 56537546 |
Informace o dalších výskytech výsledku dodaného stejným předkladatelem
| Dodáno GA ČR v roce 2014 | RIV/00216224:14330/13:00066378 v dodávce dat RIV14-GA0-14330___/01:1 |
|---|
Odkazy na výzkumné aktivity, při jejichž řešení výsledek vznikl
| Projekt podporovaný MŠMT v programu EE | EE2.3.30.0009 - Zaměstnáním čerstvých absolventů doktorského studia k vědecké excelenci (2012 - 2015) |
|---|---|
| Projekt podporovaný GA ČR v programu GA | GAP202/11/0196 - Třídy dobře strukturovaných kombinatorických objektů, šířkové parametry a návrh efektivních algoritmů (2011 - 2013) |
| Podpora / návaznosti | Specifický výzkum na vysokých školách, poskytovatel MŠMT |