Shortest paths between shortest paths
Shortest paths between shortest paths
复制标题
最短路径之间的最短路径
DOI：
10.1016/j.tcs.2011.05.021
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
Martin Milanič
中科院分区：
文献类型：
--
作者：
M. Kaminski;P. Medvedev;Martin Milanič
我们研究了图中重构最短路径的问题：给定两条最短的s-t路径，将一条转化为另一条所需的最少步骤是多少，其中每条中间路径也必须是最短的s-t路径，并且必须与前一条路径相差一个顶点。我们证明了最短的重新配置序列可以是指数的大小的图形，它是NP-困难的计算最短的重新配置序列，即使我们知道，序列的多项式长度。
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.