STRONG FAULT-TOLERANCE: PARALLEL ROUTING IN STAR NETWORKS WITH FAULTS Academic Article uri icon

abstract

  • We study the strong fault-tolerance for the star networks. Let G be a network in which all nodes have degree d. We say that G is strongly fault-tolerant if it has the following property: let Gf be a copy of G with at most d - 2 faulty nodes removed, then for any pair of non-faulty nodes u and v in Gf, there is a container of width t between u and v, where t is the minimum of degree of u and degree of v in Gf. We show that the star networks are strongly fault-tolerant and develop an algorithm that constructs a maximum width container of nearly optimal length in a star network with faults. Our algorithm requires no prior knowledge for the faulty nodes and runs in optimal time.

published proceedings

  • Journal of Interconnection Networks

author list (cited authors)

  • OH, E., & CHEN, J.

citation count

  • 28

complete list of authors

  • OH, EUNSEUK||CHEN, JIANER

publication date

  • March 2003