The Complexity of Induced Tree Reconfiguration Problems

DOI10.1007/978-3-319-30000-9_26zbMath1443.68136OpenAlexW2404019229MaRDI QIDQ2798731

Katsuhisa Yamanaka, Hiroki Arimura, Kunihiro Wasa

Publication date: 13 April 2016

Published in: Language and Automata Theory and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-30000-9_26

zbMATH Keywords

PSPACE-completenessinduced treeFPTW[1-hardness]reconfiguration problem

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Parameterized complexity, tractability and kernelization (68Q27)

Related Items (1)

Introduction to reconfiguration

This page was built for publication: The Complexity of Induced Tree Reconfiguration Problems