| Identifikační kód | RIV/00216224:14330/15:00087408 |
|---|
| Název v anglickém jazyce | Variable-Deletion Backdoors to Planning |
|---|
| Druh | D - Článek ve sborníku |
|---|
| Jazyk | eng - angličtina |
|---|
| Obor - skupina | I - Informatika |
|---|
| Obor | IN - Informatika |
|---|
| Rok uplatnění | 2015 |
|---|
| 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 | 3 |
|---|
| Počet domácích tvůrců | 1 |
|---|
| Výčet všech uvedených jednotlivých tvůrců | Martin Kronegger (státní příslušnost: AT - Rakouská republika)
Sebastian Ordyniak (státní příslušnost: DE - Spolková republika Německo, domácí tvůrce: A)
Andreas Pfandler (státní příslušnost: DE - Spolková republika Německo) |
|---|
| Popis výsledku v anglickém jazyce | Backdoors are a powerful tool to obtain efficient algorithms for hard problems. Recently, two new notions of backdoors to planning were introduced. However, for one of the new notions (i.e., variable-deletion) only hardness results are known so far. In this work we improve the situation by defining a new type of variabledeletion backdoors based on the extended causal graph of a planning instance. For this notion of backdoors several fixed-parameter tractable algorithms are identified. Furthermore, we explore the capabilities of polynomial time preprocessing, i.e., we check whether there exists a polynomial kernel. Our results also show the close connection between planning and verification problems such as Vector Addition System with States (VASS). |
|---|
| Klíčová slova oddělená středníkem | Planning; Fixed-parameter tractable algorithms; (Parameterized) complexity theory; Backdoors |
|---|
| Stránka www, na které se nachází výsledek | - |
|---|