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

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 = {s(1),s(2), ... ,s(p)} and a set of destination nodes D = {d(1), d(2), ..., d(p)} in a k-connected graph G = (V, E) with p = k, construct p paths P-i :s(i) d(ji) (1 <= i <= p) such that {j(1), j(2), ... , j(p)} = {1, 2, ... , p} and the paths Pi 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 (= 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.

Automated summary

This paper discusses the importance of the bijective connection graph and the set-to-set disjoint paths problem. It proposes an algorithm with polynomial-order time complexity for constructing disjoint paths between any pair of node sets in n-dimensional bijective connection graphs.