| Summary: | The set-to-set disjoint paths problem is to find <inline-formula> <tex-math notation="LaTeX">$n$ </tex-math></inline-formula> vertex-disjoint paths <inline-formula> <tex-math notation="LaTeX">${ \boldsymbol s}_{i}\leadsto { \boldsymbol t}_{j_{i}}$ </tex-math></inline-formula> (<inline-formula> <tex-math notation="LaTeX">$1\le i\le n$ </tex-math></inline-formula>, <inline-formula> <tex-math notation="LaTeX">$\{j_{1},j_{2},\ldots,j_{n}\}=\{1,2,\ldots,n\}$ </tex-math></inline-formula>) between two sets of vertices <inline-formula> <tex-math notation="LaTeX">$S=\{ { \boldsymbol s}_{1}, { \boldsymbol s}_{2},\ldots, { \boldsymbol s}_{n}\}$ </tex-math></inline-formula> and <inline-formula> <tex-math notation="LaTeX">$T=\{ { \boldsymbol t}_{1}, { \boldsymbol t}_{2},\ldots, { \boldsymbol t}_{n}\}$ </tex-math></inline-formula> in a graph whose connectivity is equal to <inline-formula> <tex-math notation="LaTeX">$n$ </tex-math></inline-formula>. It is a very important problem as well as the vertex-to-vertex disjoint paths problem and the vertex-to-set disjoint paths problem. In this paper, we propose an algorithm that generates <inline-formula> <tex-math notation="LaTeX">$n$ </tex-math></inline-formula> vertex-disjoint paths between two vertex sets in an <inline-formula> <tex-math notation="LaTeX">$n$ </tex-math></inline-formula>-Möbius cube. Much attention has been attracted by a Möbius cube because its diameter is almost half of that of a hypercube while it can interconnect the same number of vertices as the hypercube. We also give a proof of correctness of the algorithm and estimate that the time complexity of the algorithm is <inline-formula> <tex-math notation="LaTeX">$O(n^{6})$ </tex-math></inline-formula> and the maximum length of the paths generated by the algorithm is <inline-formula> <tex-math notation="LaTeX">$2n-2$ </tex-math></inline-formula>.
|
|---|