Parameterising the complexity of planning by the number of paths in the domain-transition graphs

MaRDI QIDQ5282951zbMATH OpenFDO

Authors Christer Bäckström

Publication date 18 July 2017

Full work available at URL http://ebooks.iospress.nl/volumearticle/36912

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• A complete parameterized complexity analysis of bounded planning
• The complexity of planning problems with simple causal graphs
• Parameterized complexity and kernel bounds for hard planning problems
• The complexity of optimal monotonic planning: the bad, the good, and the causal graph
• New islands of tractability of cost-optimal planning

Cited in

(7)

• Backdoors to planning
• A complete parameterized complexity analysis of bounded planning
• Understanding planning tasks. Domain complexity and heuristic decomposition
• The complexity of optimal monotonic planning: the bad, the good, and the causal graph
• Planning in domains with derived predicates through rule-action graphs and local search
• Parameterized complexity and kernel bounds for hard planning problems
• Cost-optimal planning, delete relaxation, approximability, and heuristics

This page was built for publication: Parameterising the complexity of planning by the number of paths in the domain-transition graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5282951)