TY - JOUR
AU - Saito, Rin
AU - Eto, Hiroshi
AU - Ito, Takehiro
AU - Uehara, Ryuhei
PY - 2024/09/10
Y2 - 2024/10/05
TI - Reconfiguration of vertex-disjoint shortest paths on graphs
JF - Journal of Graph Algorithms and Applications
JA - JGAA
VL - 28
IS - 3
SE -
DO - 10.7155/jgaa.v28i3.2973
UR - https://jgaa.info/index.php/jgaa/article/view/2973
SP - 87-101
AB - <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>
ER -