TY - GEN

T1 - Vertex-disjoint paths in the generalized hypercube under 1-restricted connectivity

AU - Wang, Guijuan

AU - Lin, Cheng Kuan

AU - Fan, Jianxi

AU - Cheng, Baolei

AU - Liu, Zhao

N1 - Publisher Copyright:
© 2019 IEEE.

PY - 2019/8

Y1 - 2019/8

N2 - The generalized hypercube is an excellent interconnection network since it includes many interconnection topologies and it can be used to construct many data center networks. Considering the probability that, in general, all neighbors of one vertex becoming faulty at the same time is extremely low, we assume that each vertex has at least one fault-free neighbor. An r-dimensional generalized hypercube is denoted by G(m-r, m-r-1,⋅, m-1). In this paper, we proposed an efficient algorithm which can construct at least κ^1(G) disjoint paths based on any two adjacent vertices in G(m-r, m-r-1, m-1) in O(rm) time where κ^1(G) is the 1-restricted connectivity of G(m-r, m-r-1, m-1). The maximum length of these disjoint paths is bounded by 7.

AB - The generalized hypercube is an excellent interconnection network since it includes many interconnection topologies and it can be used to construct many data center networks. Considering the probability that, in general, all neighbors of one vertex becoming faulty at the same time is extremely low, we assume that each vertex has at least one fault-free neighbor. An r-dimensional generalized hypercube is denoted by G(m-r, m-r-1,⋅, m-1). In this paper, we proposed an efficient algorithm which can construct at least κ^1(G) disjoint paths based on any two adjacent vertices in G(m-r, m-r-1, m-1) in O(rm) time where κ^1(G) is the 1-restricted connectivity of G(m-r, m-r-1, m-1). The maximum length of these disjoint paths is bounded by 7.

KW - 1-restricted connectivity

KW - disjoint path

KW - fault-tolerance

KW - the generalized hypercube

UR - http://www.scopus.com/inward/record.url?scp=85073514497&partnerID=8YFLogxK

U2 - 10.1109/HPCC/SmartCity/DSS.2019.00206

DO - 10.1109/HPCC/SmartCity/DSS.2019.00206

M3 - Conference contribution

AN - SCOPUS:85073514497

T3 - Proceedings - 21st IEEE International Conference on High Performance Computing and Communications, 17th IEEE International Conference on Smart City and 5th IEEE International Conference on Data Science and Systems, HPCC/SmartCity/DSS 2019

SP - 1491

EP - 1498

BT - Proceedings - 21st IEEE International Conference on High Performance Computing and Communications, 17th IEEE International Conference on Smart City and 5th IEEE International Conference on Data Science and Systems, HPCC/SmartCity/DSS 2019

A2 - Xiao, Zheng

A2 - Yang, Laurence T.

A2 - Balaji, Pavan

A2 - Li, Tao

A2 - Li, Keqin

A2 - Zomaya, Albert

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 21st IEEE International Conference on High Performance Computing and Communications, 17th IEEE International Conference on Smart City and 5th IEEE International Conference on Data Science and Systems, HPCC/SmartCity/DSS 2019

Y2 - 10 August 2019 through 12 August 2019

ER -