liu.seSearch for publications in DiVA
Change search
ReferencesLink to record
Permanent link

Direct link
A complete parameterized complexity analysis of bounded planning
Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, Faculty of Science & Engineering.
Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, Faculty of Science & Engineering.
Masaryk University, Czech Republic.
Vienna University of Technology, Austria.
2015 (English)In: Journal of computer and system sciences (Print), ISSN 0022-0000, E-ISSN 1090-2724, Vol. 81, no 7, 1311-1332 p.Article in journal (Refereed) Published
Abstract [en]

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 also determine which of the considered fixed-parameter tractable problems admit a polynomial kernel and which do not. (C) 2015 Elsevier Inc. All rights reserved.

Place, publisher, year, edition, pages
Elsevier , 2015. Vol. 81, no 7, 1311-1332 p.
Keyword [en]
Complexity of automated planning; Parameterized complexity; Kernelization
National Category
Computer and Information Science
Identifiers
URN: urn:nbn:se:liu:diva-120202DOI: 10.1016/j.jcss.2015.04.002ISI: 000356644600014OAI: oai:DiVA.org:liu-120202DiVA: diva2:842703
Note

Funding Agencies|European Research Council [239962]; Employment of Newly Graduated Doctors of Science for Scientific Excellence [CZ.1.07/2.3.00/30.0009]; Austrian Science Fund [P 26200]

Available from: 2015-07-21 Created: 2015-07-20 Last updated: 2015-07-21

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Bäckström, ChristerJonsson, Peter
By organisation
Software and SystemsFaculty of Science & Engineering
In the same journal
Journal of computer and system sciences (Print)
Computer and Information Science

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 52 hits
ReferencesLink to record
Permanent link

Direct link