| Údaje o výsledku |
| Identifikační kód | RIV/00216224:14330/13:00066378 |
| Název v původním jazyce | Kernelization Using Structural Parameters on Sparse Graph Classes |
| Druh | D - Článek ve sborníku |
| Jazyk | eng - angličtina |
| Obor | IN - Informatika |
| Rok uplatnění | 2013 |
| Kód důvěrnosti údajů | S - Úplné a pravdivé údaje nepodléhající ochraně podle zvláštních právních předpisů |
| Počet výskytů výsledku | 2 |
| Údaje z Hodnocení výsledků výzkumných organizací 2014 |
| Výsledek byl hodnocen v Pilíři I |
| Rozsah vyřazení výsledku | Tento výskyt výsledku není vyřazen |
| Zařazení výsledku v hodnocení | D - Článek ve sborníku |
| Skupina oboru v hodnocení | 04 - Technické a informatické vědy |
| Konkrétní způsob(y) hodnocení výsledku | Článek ve sborníku evidovaném v databázi Scopus bodovaný podle SJR zdroje typu Book Series nebo Conference Proceedings |
| Bodové ohodnocení | 46,181 |
| Faktor korekce | 50,1 % |
| Body (upravené podle přílohy č. 8 Metodiky) | 23,141 |
| Rozdělení výsledku mezi předkladatele |
| Organizace | Výzkumná organizace? | Podíl | Body | Body (upravené podle přílohy č. 8 Metodiky) |
|---|
| Masarykova univerzita / Fakulta informatiky | ano | 66,7 % | 30,787 | 15,427 |
|
| Tvůrci výsledku |
| Počet tvůrců celkem | 8 |
| Počet domácích tvůrců | 4 |
| Tvůrce | Gajarský Jakub (státní příslušnost: SK - Slovenská republika; A - domácí tvůrce; vedidk: 9663207) |
| Tvůrce | Hliněný Petr (státní příslušnost: CZ - Česká republika; A - domácí tvůrce; vedidk: 7595646) |
| Tvůrce | Obdržálek Jan (státní příslušnost: CZ - Česká republika; A - domácí tvůrce; vedidk: 3294099) |
| Tvůrce | Ordyniak Sebastian (státní příslušnost: DE - Spolková republika Německo; A - domácí tvůrce) |
| Tvůrce | Reidl Felix (státní příslušnost: DE - Spolková republika Německo) |
| Tvůrce | Rossmanith Peter (státní příslušnost: DE - Spolková republika Německo) |
| Tvůrce | Villaamil Fernando Sanchez (státní příslušnost: ES - Španělské království) |
| Tvůrce | Sikdar Somnath (státní příslušnost: IN - Indická republika) |
| Údaje blíže specifikující výsledek |
| Popis v původní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 these three 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 | kernelization; parameterized complexity; sparse graphs |
| Název sborníku | ESA 2013 |
| Rozsah stran | 529-540 |
| Forma vydání | P - Tištěná verze „print“ |
| ISSN | 0302-9743 |
| ISBN | 9783642404498 |
| Počet stran výsledku | 12 |
| Název nakladatele | Springer-Verlag |
| Místo vydání | Berlin Heidelberg |
| Místo konání akce | Sophia Antipolis, France |
| Rok konání akce | 2013 |
| Typ akce podle státní příslušnoti účastníků | WRD - Světová |
| DOI výsledku | 10.1007/978-3-642-40450-4_45 |
| Údaje o tomto záznamu o výsledku |
| Předkladatel | Masarykova univerzita / Fakulta informatiky |
| Dodavatel | GA0 - Grantová agentura České republiky (GA ČR) |
| Rok sběru | 2014 |
| Systémové označení dodávky dat | RIV14-GA0-14330___/01:1 |
| Specifikace | RIV/00216224:14330/13:00066378!RIV14-GA0-14330___ |
| Kontrolní kód | [CB77389468DF] |
| Další výskyty tohoto výsledku od stejného předkladatele |
| Dodáno MŠMT v roce 2014 | Záznam s identifikačním kódem RIV/00216224:14330/13:00066378 v dodávce dat RIV14-MSM-14330___/01:1 |
| Odkazy na výzkumné aktivity, při jejichž řešení výsledek vznikl |
| Projekt | EE2.3.30.0009 - Zaměstnáním čerstvých absolventů doktorského studia k vědecké excelenci (2012-2015, MSM/EE) |
| Projekt | GAP202/11/0196 - Třídy dobře strukturovaných kombinatorických objektů, šířkové parametry a návrh efektivních algoritmů (2011-2013, GA0/GA) |
| S - Specifický výzkum na vysokých školách |