Set-to-Set Disjoint Path Routing in Bijective Connection Graphs

Abstract

The bijective connection graph encompasses a family of cube-based topologies, and $n$ -dimensional bijective connection graphs include the hypercube and almost all of its variants with the order $2^{n}$ and the degree $n$ . Hence, it is important to design and implement algorithms that work in bijective connection graphs. The set-to-set disjoint paths problem is as follows: given a set of source nodes $S=\{ \boldsymbol s _{1}, \boldsymbol s _{2},\ldots, \boldsymbol s _{p}\}$ and a set of destination nodes $D=\{ \boldsymbol d _{1}, \boldsymbol d _{2},\ldots, \boldsymbol d _{p}\}$ in a $k$ -connected graph $G=(V,E)$ with $p\le k$ , construct $p$ paths $P_{i}$ : $\boldsymbol s _{i}\leadsto \boldsymbol d _{j_{i}}$ ( $1\le i\le p$ ) such that $\{j_{1},j_{2},\ldots,j_{p}\}=\{1,2,\ldots,p\}$ and the paths $P_{i}$ are node-disjoint. Finding a solution to this problem is an important issue in parallel and distributed computation as well as the node-to-node disjoint paths problem and the node-to-set disjoint paths problem. In this paper we propose an algorithm that constructs $p~(\le n)$ disjoint paths between any pair of node sets in $n$ -dimensional bijective connection graphs in polynomial-order time of $n$ . We give a proof of correctness of the algorithm as well as the estimates of the time complexity $O(n^{3}p^{4})$ and the maximum path length $n+p-1$ . According to a computer experiment in a locally twisted cube as an example of a bijective connection graph to construct $n$ disjoint paths, the average time complexity of the algorithm is $O(n^{2})$ , and the average maximum path is $0.6333n-0.266$ .

Keywords

• Dependable computing
• interconnection network
• hypercube
• multicomputer
• parallel processing
• performance evaluation supercomputers