Gajjar Kshitij, Jha Agastya Vibhuti, Kumar Manish, Lahiri Abhiruk
Indian Institute of Technology Jodhpur, Jodhpur, India.
École polytechnique fédérale de Lausanne, Lausanne, Switzerland.
Algorithmica. 2024;86(10):3309-3338. doi: 10.1007/s00453-024-01263-y. Epub 2024 Aug 27.
Reconfiguring two shortest paths in a graph means modifying one shortest path to the other by changing one vertex at a time so that all the intermediate paths are also shortest paths. This problem has several natural applications, namely: (a) repaving road networks, (b) rerouting data packets in a synchronous multiprocessing setting, (c) the shipping container stowage problem, and (d) the train marshalling problem. When modelled as graph problems, (a) is the most general case while (b), (c), (d) are restrictions to different graph classes. We show that (a) does not admit polynomial-time algorithms (assuming ), even for relaxed variants of the problem (assuming ). For (b), (c), (d), we present polynomial-time algorithms to solve the respective problems. We also generalize the problem to when at most (for a fixed integer ) contiguous vertices on a shortest path can be changed at a time.
在图中重新配置两条最短路径意味着通过一次更改一个顶点，将一条最短路径修改为另一条最短路径，使得所有中间路径也都是最短路径。这个问题有几个自然的应用，即：(a) 重新铺设道路网络，(b) 在同步多处理设置中重新路由数据包，(c) 集装箱配载问题，以及 (d) 列车编组问题。当建模为图问题时，(a) 是最一般的情况，而 (b)、(c)、(d) 是对不同图类的限制。我们证明，即使对于该问题的宽松变体（假设 ），(a) 也不存在多项式时间算法（假设 ）。对于 (b)、(c)、(d)，我们给出了求解相应问题的多项式时间算法。我们还将该问题推广到一次最多可以更改最短路径上 （对于固定整数 ）个连续顶点的情况。
