Geodesic
Reconfiguration of vertex-disjoint shortest paths on graphs
Rin Saito1 ; Hiroshi Eto2 ; Takehiro Ito1 ; Ryuhei Uehara3
1 Tohoku University
2 Kyushu Institute of Technology
3 Japan Advanced Institute of Science and Technology
Journal of Graph Algorithms and Applications, Special issue on Selected Papers from the 17th International Conference and Workshops on Algorithms and Computation, WALCOM 2023 , Tome 28 (2024) no. 3, pp. 87-101.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

We introduce and study reconfiguration problems for (internally) vertex-disjoint shortest paths: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.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. These problems generalize the well-studied Shortest Path Reconfiguration problem. In this paper, we analyze the complexity of these problems from the viewpoint of graph classes, and give some interesting contrast.
DOI : 10.7155/jgaa.v28i3.2973
Keywords: reconfiguration problems, Shortest Path Reconfiguration

Rin Saito 1 ; Hiroshi Eto 2 ; Takehiro Ito 1 ; Ryuhei Uehara 3

1 Tohoku University
2 Kyushu Institute of Technology
3 Japan Advanced Institute of Science and Technology 
@article{JGAA_2024_28_3_a6,
     author = {Rin Saito and Hiroshi Eto and Takehiro Ito and Ryuhei Uehara},
     title = {Reconfiguration of vertex-disjoint shortest paths on graphs},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {87--101},
     publisher = {mathdoc},
     volume = {28},
     number = {3},
     year = {2024},
     doi = {10.7155/jgaa.v28i3.2973},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.v28i3.2973/}
}
TY  - JOUR
AU  - Rin Saito
AU  - Hiroshi Eto
AU  - Takehiro Ito
AU  - Ryuhei Uehara
TI  - Reconfiguration of vertex-disjoint shortest paths on graphs
JO  - Journal of Graph Algorithms and Applications
PY  - 2024
SP  - 87
EP  - 101
VL  - 28
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.v28i3.2973/
DO  - 10.7155/jgaa.v28i3.2973
LA  - en
ID  - JGAA_2024_28_3_a6
ER  - 
%0 Journal Article
%A Rin Saito
%A Hiroshi Eto
%A Takehiro Ito
%A Ryuhei Uehara
%T Reconfiguration of vertex-disjoint shortest paths on graphs
%J Journal of Graph Algorithms and Applications
%D 2024
%P 87-101
%V 28
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.v28i3.2973/
%R 10.7155/jgaa.v28i3.2973
%G en
%F JGAA_2024_28_3_a6
Rin Saito; Hiroshi Eto; Takehiro Ito; Ryuhei Uehara. Reconfiguration of vertex-disjoint shortest paths on graphs. Journal of Graph Algorithms and Applications, 
							Special issue on  Selected Papers from the 17th International Conference and Workshops on Algorithms and Computation, WALCOM 2023
					, Tome 28 (2024) no. 3, pp. 87-101. doi : 10.7155/jgaa.v28i3.2973. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.v28i3.2973/

Cité par Sources :