Shortest paths between shortest paths |
| |
Authors: | Marcin Kamiński Paul Medvedev Martin Milani? |
| |
Affiliation: | a Département d’Informatique, Université Libre de Bruxelles, Brussels, Belgiumb Department of Computer Science, University of Toronto, Toronto, Canadac FAMNIT and PINT, University of Primorska, Koper, Slovenia |
| |
Abstract: | We study the following problem on reconfiguring shortest paths in graphs: Given two shortest s-t paths, what is the minimum number of steps required to transform one into the other, where each intermediate path must also be a shortest s-t path and must differ from the previous one by only one vertex. We prove that the shortest reconfiguration sequence can be exponential in the size of the graph and that it is NP-hard to compute the shortest reconfiguration sequence even when we know that the sequence has polynomial length. |
| |
Keywords: | Reconfiguration Shortest path Reconfigurability NP-hard Diameter |
本文献已被 ScienceDirect 等数据库收录! |
|