Finite Integer Index of Pathwidth and Treewidth (2014)výskyt výsledku
| Identifikační kód | RIV/00216224:14330/14:00077727 |
|---|---|
| Název v anglickém jazyce | Finite Integer Index of Pathwidth and Treewidth |
| Druh | D - Článek ve sborníku |
| Jazyk | eng - angličtina |
| Obor - skupina | I - Informatika |
| Obor | IN - Informatika |
| Rok uplatnění | 2014 |
| 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 | 1 |
| Počet tvůrců celkem | 6 |
| Počet domácích tvůrců | 3 |
| Výčet všech uvedených jednotlivých tvůrců | Sebastian Ordyniak (státní příslušnost: DE - Spolková republika Německo, domácí tvůrce: A) Jakub Gajarský (státní příslušnost: SK - Slovenská republika, domácí tvůrce: A, vedidk: 9663207) Felix Reidl (státní příslušnost: DE - Spolková republika Německo) Peter Rossmanith (státní příslušnost: DE - Spolková republika Německo) Jan Obdržálek (státní příslušnost: CZ - Česká republika, domácí tvůrce: A, vedidk: 3294099) Fernando Sánchez Vilaamil (státní příslušnost: ES - Španělské království) |
| Popis výsledku v anglickém jazyce | We show that the optimization versions of the Pathwidth and Treewidth problems have a property called finite integer index when the inputs are restricted to graphs of bounded pathwidth and bounded treewidth, respectively. They do not have this property in general graph classes. This has interesting consequences for kernelization of both these (optimization) problems on certain sparse graph classes. In the process we uncover an interesting property of path and tree decompositions, which might be of independent interest. |
| Klíčová slova oddělená středníkem | meta-kernalization; finite integer index; treewidth; pathwidth |
| Stránka www, na které se nachází výsledek | - |
| DOI výsledku | 10.1007/978-3-319-13524-3_22 |
Údaje o výsledku v závislosti na druhu výsledku
| Název sborníku | Lecture Notes in Computer Science |
|---|---|
| ISBN | 9783319135236 |
| ISSN | 0302-9743 |
| Počet stran výsledku | 12 |
| Strana od-do | 258-269 |
| Název nakladatele | Springer |
| Místo vydání | Wroclaw |
| Místo konání akce | Wroclaw |
| Datum konání akce | 10.09.2014 |
| 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 | 2015 |
| Specifikace | RIV/00216224:14330/14:00077727!RIV15-MSM-14330___ |
| Datum poslední aktualizace výsledku | 29.05.2015 |
| Kontrolní číslo | 152395088 |
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) |
|---|