Set-to-Set Disjoint Paths Problem in Möbius Cubes
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...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
IEEE
2022-01-01
|
| Series: | IEEE Access |
| Subjects: | |
| Online Access: | https://ieeexplore.ieee.org/document/9852209/ |
| _version_ | 1818486671256059904 |
|---|---|
| author | Hiroyuki Ichida Keiichi Kaneko |
| author_facet | Hiroyuki Ichida Keiichi Kaneko |
| author_sort | Hiroyuki Ichida |
| collection | DOAJ |
| description | 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>. |
| first_indexed | 2024-12-10T16:26:13Z |
| format | Article |
| id | doaj.art-c02d0ef8e0994180baeb6ca9480efd64 |
| institution | Directory Open Access Journal |
| issn | 2169-3536 |
| language | English |
| last_indexed | 2024-12-10T16:26:13Z |
| publishDate | 2022-01-01 |
| publisher | IEEE |
| record_format | Article |
| series | IEEE Access |
| spelling | doaj.art-c02d0ef8e0994180baeb6ca9480efd642022-12-22T01:41:40ZengIEEEIEEE Access2169-35362022-01-0110830758308410.1109/ACCESS.2022.31972889852209Set-to-Set Disjoint Paths Problem in Möbius CubesHiroyuki Ichida0Keiichi Kaneko1https://orcid.org/0000-0003-1790-4615Graduate School of Engineering, Tokyo University of Agriculture and Technology, Tokyo, JapanInstitute of Engineering, Tokyo University of Agriculture and Technology, Tokyo, JapanThe 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>.https://ieeexplore.ieee.org/document/9852209/Fault tolerant systemsmultiprocessor interconnection networksnetwork topologyparallel processingsupercomputers |
| spellingShingle | Hiroyuki Ichida Keiichi Kaneko Set-to-Set Disjoint Paths Problem in Möbius Cubes IEEE Access Fault tolerant systems multiprocessor interconnection networks network topology parallel processing supercomputers |
| title | Set-to-Set Disjoint Paths Problem in Möbius Cubes |
| title_full | Set-to-Set Disjoint Paths Problem in Möbius Cubes |
| title_fullStr | Set-to-Set Disjoint Paths Problem in Möbius Cubes |
| title_full_unstemmed | Set-to-Set Disjoint Paths Problem in Möbius Cubes |
| title_short | Set-to-Set Disjoint Paths Problem in Möbius Cubes |
| title_sort | set to set disjoint paths problem in m x00f6 bius cubes |
| topic | Fault tolerant systems multiprocessor interconnection networks network topology parallel processing supercomputers |
| url | https://ieeexplore.ieee.org/document/9852209/ |
| work_keys_str_mv | AT hiroyukiichida settosetdisjointpathsprobleminmx00f6biuscubes AT keiichikaneko settosetdisjointpathsprobleminmx00f6biuscubes |