| Identifikační kód | RIV/00216224:14330/13:00072819 |
|---|
| Název v anglickém jazyce | Parameterized Complexity and Kernel Bounds for Hard Planning Problems |
|---|
| Druh | D - Článek ve sborníku |
|---|
| Jazyk | eng - angličtina |
|---|
| Obor - skupina | B - Fyzika a matematika |
|---|
| Obor | BD - Teorie informace |
|---|
| 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 | 1 |
|---|
| Počet tvůrců celkem | 4 |
|---|
| Počet domácích tvůrců | 1 |
|---|
| Výčet všech uvedených jednotlivých tvůrců | Christer Backstroem (státní příslušnost: SE - Švédské království)
Peter Jonsson (státní příslušnost: SE - Švédské království)
Sebastian Ordyniak (státní příslušnost: DE - Spolková republika Německo, domácí tvůrce: A)
Stefan Szeider (státní příslušnost: AT - Rakouská republika) |
|---|
| Popis výsledku v anglické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 $eleq 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 byGuo, 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 oddělená středníkem | bounded planning; parameterized complexity; kernelization |
|---|
| Stránka www, na které se nachází výsledek | - |
|---|
| DOI výsledku | 10.1007/978-3-642-38233-8_2 |
|---|