HIGHLY FAULT-TOLERANT ROUTINGS AND FAULT-INDUCED DIAMETER FOR GENERALIZED HYPERCUBE GRAPHS

Consider a communication network G in which a limited number of link a nd/or node faults F might occur, A routing rho for the network (a fixe d path between each pair of nodes) must be chosen without knowing whic h components might become faulty, The diameter of the surviving route graph R(G, rho)/F, where the surviving route graph R(G, rho)/F is a di rected graph consisting of all nonfaulty nodes in G with a directed ed ge from x to y iff there are no faults on the route from x to y, could be one of the fault-tolerant measures for the routing rho, In this pa per, we show that we can construct efficient and highly fault-tolerant routings on a k-dimensional generalized d-hyperlube C(d, k) such that the diameter of the surviving route graph is bounded by constant for the case that the number of faults exceeds the connectivity of C(d, k) , (C) 1997 Academic Press.