4.6 Article

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

Journal

IEEE ACCESS
Volume 10, Issue -, Pages 72731-72742

Publisher

IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
DOI: 10.1109/ACCESS.2022.3188783

Keywords

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

Funding

  1. Japan Society for the Promotion of Science [20K11729, 19K11887]

Ask authors/readers for more resources

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.
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.

Authors

I am an author on this paper
Click your name to claim this paper and add it to your profile.

Reviews

Primary Rating

4.6
Not enough ratings

Secondary Ratings

Novelty
-
Significance
-
Scientific rigor
-
Rate this paper

Recommended

No Data Available
No Data Available