Set-to-Set Disjoint Paths Problem in Möbius Cubes
Authors:
Open Access
- 8 August 2022
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Access
- Vol. 10, 83075-83084
Abstract
The set-to-set disjoint paths problem is to find $n$ vertex-disjoint paths ${ \boldsymbol s}_{i}\leadsto { \boldsymbol t}_{j_{i}}$ ( $1\le i\le n$ , $\{j_{1},j_{2},\ldots,j_{n}\}=\{1,2,\ldots,n\}$ ) between two sets of vertices $S=\{ { \boldsymbol s}_{1}, { \boldsymbol s}_{2},\ldots, { \boldsymbol s}_{n}\}$ and $T=\{ { \boldsymbol t}_{1}, { \boldsymbol t}_{2},\ldots, { \boldsymbol t}_{n}\}$ in a graph whose connectivity is equal to $n$ . 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 $n$ vertex-disjoint paths between two vertex sets in an $n$ -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 $O(n^{6})$ and the maximum length of the paths generated by the algorithm is $2n-2$ .Keywords
Funding Information
- Grant-in-Aid for Scientific Research (C) of the Japan Society for the Promotion of Science (19K11887, 20K11729)
This publication has 51 references indexed in Scilit:
- Many-to-many disjoint paths in faulty hypercubesInformation Sciences, 2009
- Constructing the nearly shortest path in crossed cubesInformation Sciences, 2009
- Pancyclicity of Möbius cubes with faulty nodesMicroprocessors and Microsystems, 2006
- Constructing one-to-many disjoint paths in folded hypercubesIEEE Transactions on Computers, 2002
- An efficient algorithm for k-pairwise disjoint paths in star graphsInformation Processing Letters, 1998
- Embedding binary trees into crossed cubesIEEE Transactions on Computers, 1995
- The Mobius cubesIEEE Transactions on Computers, 1995
- The crossed cube architecture for parallel computationIEEE Transactions on Parallel and Distributed Systems, 1992
- Properties and performance of folded hypercubesIEEE Transactions on Parallel and Distributed Systems, 1991
- The cosmic cubeCommunications of the ACM, 1985