Fault-Tolerant Graphs for Hypercubes and Tori*

Toshinori YAMADA  Koji YAMAMOTO  Shuichi UENO  

IEICE TRANSACTIONS on Information and Systems   Vol.E79-D   No.8   pp.1147-1152
Publication Date: 1996/08/25
Online ISSN: 
Print ISSN: 0916-8532
Type of Manuscript: Special Section PAPER (Special Issue on Architectures, Algorithms and Networks for Massively Parallel Computing)
Category: Fault Diagnosis/Tolerance
hypercubes,  tori,  edge-fault-tolerant graphs,  matric graphs,  error-correcting binary linear codes,  

Full Text: PDF>>
Buy this Article

Motivated by the design of fault-tolerant multiprocessor interconnection networks, this paper considers the following problem: Given a positive integer t and a graph H, construct a graph G from H by adding a minimum number Δ(t, H) of edges such that even after deleting any t edges from G the remaining graph contains H as a subgraph. We estimate Δ(t, H) for the hypercube and torus, which are well-known as important interconnection networks for multiprocessor systems. If we denote the hypercube and the square torus on N vertices by QN and DN respectively, we show, among others, that Δ(t, QN) = O(tN log(log N/t + log 2e)) for any t and N (t 2), and Δ(1, DN) = N/2 for N even.