Journal
THEORETICAL COMPUTER SCIENCE
Volume 957, Issue -, Pages -Publisher
ELSEVIER
DOI: 10.1016/j.tcs.2023.113855
Keywords
Interconnection networks; Reliability and fault-tolerance; Edge-disjoint paths; Pil-conditional edge-connectivity; (nk)-Enhanced hypercube
Categories
Ask authors/readers for more resources
One of the most important issues in interconnection networks is finding edge-disjoint paths that transmit information, and this paper offers a unified method to determine the minimum cardinalities of faulty links in a specific interconnection network topology. The minimum cardinalities of faulty links in this topology share the same value under different link-faulty assumptions, except for a specific case. The findings provide refined measurements for the reliability and fault-tolerance of interconnection networks.
One of the most central issues in interconnection networks of parallel and distributed systems is finding edge-disjoint paths that transmit information. Finding as many as possible many-to-many edge-disjoint paths is conducive to improving the fault-tolerance of such networks. As an interconnection network topology, (n, k)-enhanced hypercube Qn,k (1 < k < n -1), is a momentous variant of well-known hypercube. For integers 1 < l < n -1 and n >= 2, let delta = 0 if 1 < l < n -k, and delta =1 if n -k + 1 < l < n -1. This paper offers a unified method to determine the minimum cardinalities of faulty links in Qn,k, whose malfunction divides this network into several connected components such that each processor has at least l + delta neighbors, each component contains no less than 2l processors and the number of average neighbors for all processors is at least l + delta, respectively. Under these three different link-faulty assumptions, but for the condition of k = 2 and l = n - 2, the minimum cardinalities of such faulty links share the same value (n - l - delta + 1)2l. And the value in the exceptional case is (n - l - delta)2l+1 = 2n-1. In other words, we find the maximum numbers of many-to-many edge-disjoint paths of Qn,k under the above three hypotheses, which offers refined measurements for the reliability and fault-tolerance of interconnection networks. (c) 2023 Elsevier B.V. All rights reserved.
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