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 -