Highly Fault-Tolerant Routings and Fault-Induced Diameter for Generalized Hypercube Graphs
✍ Scribed by Koichi Wada; Takaharu Ikeo; Kimio Kawaguchi; Wei Chen
- Publisher
- Elsevier Science
- Year
- 1997
- Tongue
- English
- Weight
- 130 KB
- Volume
- 43
- Category
- Article
- ISSN
- 0743-7315
No coin nor oath required. For personal study only.
✦ Synopsis
Consider a communication network G in which a limited number of link and/or node faults F might occur. A routing ρ for the network (a fixed path between each pair of nodes) must be chosen without knowing which components might become faulty. The diameter of the surviving route graph R(G, ρ)/F, where the surviving route graph R(G, ρ)/F is a directed graph consisting of all nonfaulty nodes in G with a directed edge 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 ρ. In this paper, we show that we can construct efficient and highly fault-tolerant routings on a k-dimensional generalized d-hypercube 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).