@article{Saito_Eto_Ito_Uehara_2024, title={Reconfiguration of vertex-disjoint shortest paths on graphs}, volume={28}, url={https://jgaa.info/index.php/jgaa/article/view/2973}, DOI={10.7155/jgaa.v28i3.2973}, abstractNote={<p>We introduce and study reconfiguration problems for (internally) vertex-disjoint shortest paths:<br>Given two tuples of internally vertex-disjoint shortest paths for fixed terminal pairs in an unweighted graph, we are asked to determine whether one tuple can be transformed into the other by exchanging a single vertex of one shortest path in the tuple at a time, so that all intermediate results remain tuples of internally vertex-disjoint shortest paths.<br>We also study the shortest variant of the problem, that is, we wish to minimize the number of vertex-exchange steps required for such a transformation, if exists. <br>These problems generalize the well-studied Shortest Path Reconfiguration problem. <br>In this paper, we analyze the complexity of these problems from the viewpoint of graph classes, and give some interesting contrast.</p>}, number={3}, journal={Journal of Graph Algorithms and Applications}, author={Saito, Rin and Eto, Hiroshi and Ito, Takehiro and Uehara, Ryuhei}, year={2024}, month={Sep.}, pages={87–101} }