A complete parameterized complexity analysis of bounded planning
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F15%3A00087406" target="_blank" >RIV/00216224:14330/15:00087406 - isvavai.cz</a>
Result on the web
<a href="http://dx.doi.org/10.1016/j.jcss.2015.04.002" target="_blank" >http://dx.doi.org/10.1016/j.jcss.2015.04.002</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1016/j.jcss.2015.04.002" target="_blank" >10.1016/j.jcss.2015.04.002</a>
Alternative languages
Result language
angličtina
Original language name
A complete parameterized complexity analysis of bounded planning
Original language description
The propositional planning problem is a notoriously difficult computational problem, which remains hard even under strong syntactical and structural restrictions. Given its difficulty it becomes natural to study planning in the context of parameterized complexity. In this paper we continue the work initiated by Downey, Fellows and Stege on the parameterized complexity of planning with respect to the parameter "length of the solution plan." We provide a complete classification of the parameterized complexity of the planning problem under two of the most prominent syntactical restrictions, i.e., the so called PUBS restrictions introduced by Backstrom and Nebel and restrictions on the number of preconditions and effects as introduced by Bylander. We alsodetermine which of the considered fixed-parameter tractable problems admit a polynomial kernel and which do not.
Czech name
—
Czech description
—
Classification
Type
J<sub>x</sub> - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)
CEP classification
IN - Informatics
OECD FORD branch
—
Result continuities
Project
<a href="/en/project/EE2.3.30.0009" target="_blank" >EE2.3.30.0009: Employment of Newly Graduated Doctors of Science for Scientific Excellence</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2015
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Name of the periodical
Journal of Computer and System Sciences
ISSN
0022-0000
e-ISSN
—
Volume of the periodical
81
Issue of the periodical within the volume
7
Country of publishing house
US - UNITED STATES
Number of pages
22
Pages from-to
1311-1332
UT code for WoS article
000356644600014
EID of the result in the Scopus database
—