On the Complexity of Reconfiguration Problems

DOI10.1007/978-3-540-92182-0_6zbMath1183.68310OpenAlexW1735730262MaRDI QIDQ3596704

Takehiro Ito, Erik D. Demaine, Ryuhei Uehara, Yushi Uno, Nicholas J. A. Harvey, Christos H. Papadimitriou, Martha Sideris

Publication date: 29 January 2009

Published in: Algorithms and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-92182-0_6

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (8)

Reconfiguration of List Edge-Colorings in a Graph ⋮ Congestion-Free Rerouting of Flows on DAGs ⋮ The complexity of rerouting shortest paths ⋮ On the complexity of reconfiguration problems ⋮ Unnamed Item ⋮ Shortest Paths between Shortest Paths and Independent Sets ⋮ Shortest paths between shortest paths ⋮ Inferring local transition functions of discrete dynamical systems from observations of system behavior

This page was built for publication: On the Complexity of Reconfiguration Problems