The Constructive Algorithm of Vertex-disjoint Paths in the Generalized Hypercube under Restricted Connectivity

Guijuan Wang,
Jianxi Fan,
Yali Lv,
Baolei Cheng,
Shuangxiang Kan,

Abstract


The generalized hypercube is a classical interconnection network with excellent properties. It not only includes the hypercube network, the 3-ary n-cube network, and the complete networks, but also can be used to construct data center networks such as FBFLY, BCube, HyperX, SWCube, etc. Since the fact that all neighbors of one vertex becoming faulty at the same time is almost impossible, we assume that each vertex in this paper has at least one fault-free neighbor. We use G(m, m_r-1,...,m_1) to denote the r-dimensional generalized hypercube and k^1(G) to denote the 1-restricted connectivity of G(m, m_r-1,...,m_1). Then we design an algorithm to construct at least k^1(G) disjoint paths based on any two distinct vertices in G(m, m_r-1,...,m_1) under the 1-restricted connectivity. The maximum length of these disjoint paths is bounded by r+2 .


Citation Format:
Guijuan Wang, Jianxi Fan, Yali Lv, Baolei Cheng, Shuangxiang Kan, "The Constructive Algorithm of Vertex-disjoint Paths in the Generalized Hypercube under Restricted Connectivity," Journal of Internet Technology, vol. 20, no. 6 , pp. 1995-2006, Nov. 2019.

Full Text:

PDF

Refbacks

  • There are currently no refbacks.





Published by Executive Committee, Taiwan Academic Network, Ministry of Education, Taipei, Taiwan, R.O.C
JIT Editorial Office, Library and Information Center, National Dong Hwa University
No. 1, Sec. 2, Da Hsueh Rd. Shoufeng, Hualien 97401, Taiwan, R.O.C.
Tel: +886-3-931-7017  E-mail: jit.editorial@gmail.com