ON MINIMUM FAULT-TOLERANT NETWORKS

Citation
S. Ueno et al., ON MINIMUM FAULT-TOLERANT NETWORKS, SIAM journal on discrete mathematics, 6(4), 1993, pp. 565-574
Citations number
14
Categorie Soggetti
Mathematics,Mathematics
ISSN journal
08954801
Volume
6
Issue
4
Year of publication
1993
Pages
565 - 574
Database
ISI
SICI code
0895-4801(1993)6:4<565:OMFN>2.0.ZU;2-1
Abstract
This paper considers the following problem: Given a positive integer t and graph H, construct a graph G from H by adding a minimum number DE LTA(t, H) (respectively, DELTA'(t, H)) of edges and an appropriate num ber of vertices, such that after removing any t vertices (respectively , t edges) from G the remaining graph contains H as a subgraph. This p roblem was motivated by the design of fault-tolerant interconnection n etworks for multiprocessor systems. The authors estimate DELTA(t, H) a nd DELTA'(t, H) for the cycle, path, complete binary tree, grid, torus , and hypercube on n vertices.