A complete parameterized complexity analysis of bounded planning
From MaRDI portal
Publication:2353405
DOI10.1016/j.jcss.2015.04.002zbMath1320.68096arXiv1310.7828OpenAlexW2071900144MaRDI QIDQ2353405
Peter Jonsson, Stefan Szeider, Sebastian Ordyniak, Christer Bäckström
Publication date: 13 July 2015
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1310.7828
Related Items (7)
Decidability and complexity of action-based temporal planning over dense time ⋮ On Structural Parameterizations of the Bounded-Degree Vertex Deletion Problem ⋮ On structural parameterizations of the bounded-degree vertex deletion problem ⋮ Cost-optimal Planning, Delete Relaxation, Approximability, and Heuristics ⋮ Refining complexity analyses in planning by exploiting the exponential time hypothesis ⋮ A framework for analysing state-abstraction methods ⋮ Backdoors to planning
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Fundamentals of parameterized complexity
- Solving MAX-\(r\)-SAT above a tight lower bound
- FPT algorithms for connected feedback vertex set
- Complexity results for standard benchmark domains in planning
- Causal graphs and structurally restricted planning
- On problems without polynomial kernels
- State-variable planning under structural restrictions: algorithms and complexity
- On the complexity of blocks-world planning
- Tractable plan existence does not imply tractable plan generation
- The computational complexity of propositional STRIPS planning
- The Turing way to parameterized complexity
- On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems
- Strong bounds on the approximability of two Pspace-hard problems in propositional planning
- Parametrized complexity theory.
- A probabilistic analysis of propositional STRIPS planning
- Algorithms and Limits for Compact Plan Representations
- The Causal Graph Revisited for Directed Model Checking
- The Lost Continent of Polynomial Time: Preprocessing and Kernelization
- Kernelization: New Upper and Lower Bound Techniques
- Parameterized Complexity and Kernel Bounds for Hard Planning Problems
- Kernelization Lower Bounds by Cross-Composition
- The Parameterized Complexity of Domination-Type Problems and Application to Linear Codes
This page was built for publication: A complete parameterized complexity analysis of bounded planning
