| Údaje o výsledku |
| Identifikační kód | RIV/00216224:14330/13:00072819 |
| Název v původním jazyce | Parameterized Complexity and Kernel Bounds for Hard Planning Problems |
| Druh | D - Článek ve sborníku |
| Jazyk | eng - angličtina |
| Obor | BD - Teorie informace |
| 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 | 1 |
| Ú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 | 40,0 % | 18,472 | 9,256 |
|
| Tvůrci výsledku |
| Počet tvůrců celkem | 4 |
| Počet domácích tvůrců | 1 |
| Tvůrce | Backstroem Christer (státní příslušnost: SE - Švédské království) |
| Tvůrce | Jonsson Peter (státní příslušnost: SE - Švédské království) |
| Tvůrce | Ordyniak Sebastian (státní příslušnost: DE - Spolková republika Německo; A - domácí tvůrce) |
| Tvůrce | Szeider Stefan (státní příslušnost: AT - Rakouská republika) |
| Údaje blíže specifikující výsledek |
| Popis v původním jazyce | The propositional planning problem is a notoriously difficult computational problem. Downey, Fellows and Stege initiated the parameterized analysis of planning (with plan length as the parameter) and B\"{a}ckstr\"{o}m et al. picked up this line of research and provided an extensive parameterized analysis under various restrictions, leaving open only one stubborn case. We continue this work and provide a full classification. In particular, we show that the case when actions have no preconditions and at most $e$ postconditions is fixed-parameter tractable if $e\leq 2$ and W[1]-complete otherwise. We show fixed-parameter tractability by a reduction to a variant of the Steiner Tree problem; this problem has recently been shown fixed-parameter tractable by Guo, Niedermeier and Suchy. If a problem is fixed-parameter tractable, then it admits a polynomial-time self-reduction to instances whose input size is bounded by a function of the parameter, called the kernel. |
| Klíčová slova | bounded planning; parameterized complexity; kernelization |
| Název sborníku | Lecture Notes in Computer Science |
| Rozsah stran | 13-24 |
| Forma vydání | P - Tištěná verze „print“ |
| ISSN | 0302-9743 |
| Počet stran výsledku | 12 |
| ISBN | 9783642382321 |
| Název nakladatele | Springer-Verlag |
| Místo vydání | Germany |
| Místo konání akce | Barcelona, Spain |
| 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-38233-8_2 |
| Údaje o tomto záznamu 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 |
| Systémové označení dodávky dat | RIV14-MSM-14330___/01:1 |
| Specifikace | RIV/00216224:14330/13:00072819!RIV14-MSM-14330___ |
| Kontrolní kód | [ECF1C0E993F7] |
| Jiný výskyt tohoto výsledku se v RIV nenachází |
| 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) |