2021/12/14 by Kshitij Gajjar, Agastya Vibhuti Jha, Gajjar, Kshitij +5
Computer Science · Engineering · #05C85 #68Q25 #68T99 #Advanced Graph Theory Research #Artificial Intelligence (cs.AI) #Data Management and Algorithms #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #F.2.2 #FOS: Computer and information sciences #Vehicle Routing Optimization Methods
paper · pdf · doi:10.48550/arxiv.2112.07499
openalex publication_date 2021/12/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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) revamping road networks, (b) rerouting data packets in 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) and (d) are restrictions to different graph classes. We show that (a) is intractable, even for relaxed variants of the problem. For (b), (c) and (d), we present efficient algorithms to solve the respective problems. We also generalize the problem to when at most k (for a fixed integer k≥ 2) contiguous vertices on a shortest path can be changed at a time.