A complete parameterized complexity analysis of bounded planning
type: Item
instance of: scholarly article
title: A complete parameterized complexity analysis of bounded planning
zbMATH Open document ID: 1320.68096
author: Peter Jonsson
author: Sebastian Ordyniak
author: Stefan Szeider
author: Christer Bäckström
published in: Journal of Computer and System Sciences
publication date: 2015-07-13T00:00:00Z
full work available at URL: https://arxiv.org/abs/1310.7828
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 6458554
zbMATH Keywords: complexity of automated planning
zbMATH Keywords: parameterized complexity
zbMATH Keywords: kernelization
MaRDI profile type: Publication
OpenAlex ID: W2071900144
arXiv ID: 1310.7828
cites work: Solving MAX-\(r\)-SAT above a tight lower bound
cites work: Q3457202
cites work: Q3457201
cites work: Algorithms and limits for compact plan representations
cites work: Parameterized Complexity and Kernel Bounds for Hard Planning Problems
cites work: Kernelization: New Upper and Lower Bound Techniques
cites work: On problems without polynomial kernels
cites work: Kernelization Lower Bounds by Cross-Composition
cites work: Q4411159
cites work: The computational complexity of propositional STRIPS planning
cites work: A probabilistic analysis of propositional STRIPS planning
cites work: The Parameterized Complexity of Domination-Type Problems and Application to Linear Codes
cites work: The Turing way to parameterized complexity
cites work: Causal graphs and structurally restricted planning
cites work: Q4263467
cites work: Q4393480
cites work: Fundamentals of parameterized complexity
cites work: Q4449303
cites work: The Lost Continent of Polynomial Time: Preprocessing and Kernelization
cites work: Parametrized complexity theory.
cites work: Q5313998
cites work: Q3624119
cites work: On the complexity of blocks-world planning
cites work: Complexity results for standard benchmark domains in planning
cites work: Q3624014
cites work: Strong bounds on the approximability of two Pspace-hard problems in propositional planning
cites work: State-variable planning under structural restrictions: algorithms and complexity
cites work: Tractable plan existence does not imply tractable plan generation
cites work: FPT algorithms for connected feedback vertex set
cites work: On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems
cites work: The Causal Graph Revisited for Directed Model Checking
DOI: 10.1016/J.JCSS.2015.04.002
description: scientific article