Premium
Optimally edge fault‐tolerant trees
Author(s) -
Ku HungKuei,
Hayes John P.
Publication year - 1996
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/(sici)1097-0037(199605)27:3<203::aid-net5>3.0.co;2-m
Subject(s) - fault tolerance , computer science , multiprocessing , graph , combinatorics , enhanced data rates for gsm evolution , spare part , discrete mathematics , graph theory , mathematics , algorithm , parallel computing , distributed computing , engineering , mechanical engineering , telecommunications
We study the structure of fault‐tolerant multiprocessor systems that allow one or more communication links to fail. Spare links are employed to tolerate link failures; no redundant processing units are required. Such a multiprocessor is modeled by a graph G whose nodes and edges correspond to the processing units and the links, respectively. G is a k ‐edge fault‐tolerant design of a basic graph H, denoted k ‐EFT( H ), if every graph obtained by removing any k edges from G embeds H. If G contains the fewest edges among all k ‐EFT designs of H, then G is said to be optimally k ‐EFT with respect to H. We introduce the concept of critical edges and graphs and derive some of their properties that are generally useful in designing optimal EFT supergraphs. We investigate the theory of edge fault tolerance for tree‐structured networks, in particular, nonhomogeneous trees and stars. For both cases, we obtain optimal k ‐EFT designs for all k. © 1996 John Wiley & Sons, Inc.