Journal
IEEE ACCESS
Volume 10, Issue -, Pages 72731-72742Publisher
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
DOI: 10.1109/ACCESS.2022.3188783
Keywords
Dependable computing; interconnection network; hypercube; multicomputer; parallel processing; performance evaluation supercomputers
Categories
Funding
- 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
Recommended
No Data Available