Premium
Fault‐tolerant graphs for tori
Author(s) -
Yamada Toshinori,
Ueno Shuichi
Publication year - 1998
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(199810)32:3<181::aid-net2>3.0.co;2-g
Subject(s) - multiprocessing , interconnection , torus , graph , computer science , combinatorics , fault tolerance , mathematics , parallel computing , discrete mathematics , distributed computing , computer network , geometry
Abstract 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 torus, which is well known as a very important interconnection network for multiprocessor systems. © 1998 John Wiley & Sons, Inc. Networks 32: 181–188, 1998