For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
On Dynamic Fault Tolerance for WSI Networks
Toshinori YAMADA Tomohiro NISHIMURA Shuichi UENO
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 1997/08/25
Print ISSN: 0916-8508
Type of Manuscript: LETTER
Category: Graphs and Networks
WSI networks, dynamic fault tolerance, finitely reconfigurability, locally reconfigurability,
Full Text: PDF>>
The finite reconfigurability and local reconfigurability of graphs were proposed by Sha and Steiglitz ,  in connection with a problem of on-line reconfiguraion of WSI networks for run-time faults. It is shown in  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.