Parallel routing in hypercube networks with faulty nodes
Eunseuk Oh, Jianer Chen · 2002
The concept of strong fault-tolerance was introduced to characterize the property of parallel routing. A network G of degree d is said to be strongly fault-tolerant if with at most d-2 faulty nodes, any two nodes u and v in G are connected by min{deg/sub f/(u), deg/sub f/(v)} node-disjoint paths, where deg/sub f/ (u) and deg/sub f/ (v) are the numbers of non-faulty neighbors of the nodes u and v in G, respectively. We show that the hypercube networks are strongly fault-tolerant and develop an algorithm that constructs the maximum number of node-disjoint paths in a hypercube network with faults. Our algorithm is optimal in terms of time and length of node-disjoint paths.