Další formáty:
BibTeX
LaTeX
RIS
@inproceedings{1344311,
author = {Kronegger, Martin and Ordyniak, Sebastian and Pfandler, Andreas},
address = {Austin; United States},
booktitle = {Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence},
keywords = {Planning; Fixed-parameter tractable algorithms; (Parameterized) complexity theory; Backdoors},
howpublished = {tištěná verze "print"},
language = {eng},
location = {Austin; United States},
isbn = {978-1-57735-703-2},
pages = {3305-3312},
publisher = {AI Access Foundation},
title = {Variable-Deletion Backdoors to Planning},
url = {https://www.aaai.org/ocs/index.php/AAAI/AAAI15/paper/view/9885},
year = {2015}
}
TY - JOUR
ID - 1344311
AU - Kronegger, Martin - Ordyniak, Sebastian - Pfandler, Andreas
PY - 2015
TI - Variable-Deletion Backdoors to Planning
PB - AI Access Foundation
CY - Austin; United States
SN - 9781577357032
KW - Planning
KW - Fixed-parameter tractable algorithms
KW - (Parameterized) complexity theory
KW - Backdoors
UR - https://www.aaai.org/ocs/index.php/AAAI/AAAI15/paper/view/9885
N2 - 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).
ER -
KRONEGGER, Martin, Sebastian ORDYNIAK a Andreas PFANDLER. Variable-Deletion Backdoors to Planning. In \textit{Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence}. Austin; United States: AI Access Foundation, 2015, s.~3305-3312. ISBN~978-1-57735-703-2.
|
