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

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 .