Set-to-Set Disjoint Path Routing in Bijective Connection Graphs
Keiichi Kaneko, Antoine Bossard, Frederick C. Harris · IEEE Access · 2022
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$.