A Fault-Free Unicast Algorithm in the Generalized Hypercube with Restricted Faulty Vertices

摘要

The generalized hypercube is a highly-connective network proposed by Bhuyan and Agrawal. In this paper, we study the restricted connectivity and fault-free unicast algorithm in the generalized hypercube. Firstly, we prove that the restricted connectivity of a r-dimensional generalized hypercube G(m(r),m(r-1),...,m(1)) is 2 kappa(G) - n, where kappa (G) denotes the connectivity of G(m(r),m(r-1),...,m(1)) and n = max {m(1),m(2),...,m(r)}, under the condition that each vertex has at least one fault-free neighbor. It is almost twice the traditional connectivity of G(m(r),m(r-1),...,m(1)). Furthermore, we present an O(kappa(G)(3)) fault-free unicast algorithm in the generalized hypercube.