Parallel routing in hypercube networks with faulty nodes Conference Paper uri icon

abstract

  • The concept of strong fault-tolerance was introduced to characterize the property of parallel routing [15]. A network G of degree d is said strongly fault-tolerant if with at most d - 2 faulty nodes, any two nodes u and v in G are connected by min{degf(u), degf(v)} node-disjoint paths, where degf(u) and degf(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.

name of conference

  • Eigth International Conference on Parallel and Distributed Systems, ICPADS 2001, KyongJu City, Korea, June 26-29, 2001

published proceedings

  • Proceedings of the Internatoinal Conference on Parallel and Distributed Systems - ICPADS

author list (cited authors)

  • Oh, E., & Chen, J.

complete list of authors

  • Oh, E||Chen, J

publication date

  • January 2001