On Dynamic Fault Tolerance for WSI Networks

Toshinori YAMADA  Tomohiro NISHIMURA  Shuichi UENO  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E80-A   No.8   pp.1529-1530
Publication Date: 1997/08/25
Online ISSN: 
Print ISSN: 0916-8508
Type of Manuscript: LETTER
Category: Graphs and Networks
WSI networks,  dynamic fault tolerance,  finitely reconfigurability,  locally reconfigurability,  

Full Text: PDF>>
Buy this Article

The finite reconfigurability and local reconfigurability of graphs were proposed by Sha and Steiglitz [1], [2] in connection with a problem of on-line reconfiguraion of WSI networks for run-time faults. It is shown in [2] that a t-locally-reconfigurable graph for a 2-dimensional N-vertex array AN can be constructed from AN by adding O(N) vertices and edges. We show that Ω(N) vertices must be added to an N-vertex graph GN in order to construct a t-locally-reconfigurable graph for GN, which means that the number of added vertices for the above mentioned t-locally-reconfigurable graph for AN is optimal to within a constant factor. We also show that a t-finitely-reconfigurable graph for an N-vertex graph GN can be constructed from GN by adding t vertices and tN + t (t+1)/2 edges.