On Dynamic Fault Tolerance for WSI Networks
Summary :
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.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E80-A No.8 pp.1529-1530
- Publication Date
- 1997/08/25
- Publicized
- Online ISSN
- DOI
- Type of Manuscript
- Category
- Graphs and Networks
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Toshinori YAMADA, Tomohiro NISHIMURA, Shuichi UENO, "On Dynamic Fault Tolerance for WSI Networks" in IEICE TRANSACTIONS on Fundamentals,
vol. E80-A, no. 8, pp. 1529-1530, August 1997, doi: .
Abstract: 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.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e80-a_8_1529/_p
Copy
@ARTICLE{e80-a_8_1529,
author={Toshinori YAMADA, Tomohiro NISHIMURA, Shuichi UENO, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={On Dynamic Fault Tolerance for WSI Networks},
year={1997},
volume={E80-A},
number={8},
pages={1529-1530},
abstract={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.},
keywords={},
doi={},
ISSN={},
month={August},}
Copy
TY - JOUR
TI - On Dynamic Fault Tolerance for WSI Networks
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1529
EP - 1530
AU - Toshinori YAMADA
AU - Tomohiro NISHIMURA
AU - Shuichi UENO
PY - 1997
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E80-A
IS - 8
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - August 1997
AB - 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.
ER -
English
