Strong Fault-Tolerance: Parallel Routing in Networks with Faults Conference Paper uri icon

abstract

  • Springer-Verlag Berlin Heidelberg 2001. A d-regular network G is strongly fault-tolerant if for any copy Gf of G with at most d 2 faulty nodes, every pair of non-faulty nodes u and v in Gf admits min{df (u), df (v) node-disjoint paths in Gf from u to v, where df (u) and df (v) are the degrees of the nodes u and v in Gf. We show that popular network structures, such as hyper- cube and star networks, are strongly fault-tolerant. We develop efficient algorithms that construct the maximum number of node-disjoint paths of optimal or nearly optimal length in these networks with faulty nodes. Our algorithms are optimal in terms of their running time.

name of conference

  • Computational Science - ICCS 2001, International Conference, San Francisco, CA, USA, May 28-30, 2001. Proceedings, Part II

published proceedings

  • Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

author list (cited authors)

  • Chen, J., & Oh, E.

citation count

  • 0

complete list of authors

  • Chen, Jianer||Oh, Eunseuk

publication date

  • January 2001