On Dynamic Fault Tolerance for WSI Networks

概要

論文の詳細を見る
The finite reconfigurability and local reconfigurability of graphs were proposed by Sha and Steiglitz [1], [2] in connection with a problem of on-line reconfiguration 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 A_N can be constructed from A_N by adding O(N) vertices and edges. We show that Ω(N) vertices must be added to an N-vertex graph G_N in order to construct a t-locally-reconfigurable graph for G_N, which means that the number of added vertices for the above mentioned t-locally-reconfigurable graph for A_N 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.
社団法人電子情報通信学会の論文
1997-08-25

著者

UENO Shuichi
Department of Communication and Integrated Systems, Tokyo Institute of Technology
NISHIMURA TOMOHIRO
Department of Geology and Mineralogy, Graduate School of Science, Kyoto University
YAMADA Toshinori
Department of Physical Electronics, Tokyo Institute of Technology
Yamada Toshinori
Department Of Physical Electronics Tokyo Institute Of Technology
Yamada Toshinori
Department Of Applied Chemistry Institute Of Colloid And Interface Science Science University Of Tok
Nishimura Tomohiro
Graduate School Of Materials Science Kara Institute Of Science And Technology
Nishimura Tomohiro
Department Of Physical Electronics Tokyo Institute Of Technology
Ueno Shuichi
Department Of Communication And Integrated Systems Tokyo Institute Of Technology
Ueno Shuichi
Department Of Biological Science Faculty Of Science Yamaguchi University
Ueno Shuichi
Department Of Physical Electronics Tokyo Institute Of Technology

関連論文

Proposal and Preliminary Experiments of Indoor Optical Wireless LAN Based on a CMOS Image Sensor with a High-Speed Readout Function Enabling a Low-Power Compact Module with Large Uplink Capacity(The IEICE Transactions on Communications, Vol.E86-B, No.5)
On Two Problems of Nano-PLA Design
A Note on Two Problems of Nano-PLA Design
A Note on Two Problems of Nano-PLA Design
A Note on Two Problems of Nano-PLA Design
Gene expression profiling of human myocardium with atrial fibrillation by DNA microarray analysis
Cardioprotective effects of angiotensin II receptor blockade on the molecular responses induced by mechanical stress in cardiac myocytes
DNA microarray analysis of the in vivo progression mechanism for heart failure in Dahl salt-sensitive rats
On the Complexity of Fault Testing for Reversible Circuits
A-1-26 On the Complexity of Fault Testing for Reversible Circuits
Analytical Device Model of SOI MOSFETs Including Self-Heating Effect
First discovery of Pravitoceras sigmoidale Yabe from the Yezo Supergroup in Hokkaido, Japan
Ontogenetic shell development of a Cretaceous desmoceratine ammonoid "Tragodesmoceroides subcostatus" Matsumoto, 1942 from Hokkaido, Japan
Proposal and Preliminary Experiments of Indoor Optical Wireless LAN Based on a CMOS Image Sensor with a High-Speed Readout Function Enabling a Low-Power Compact Module with Large Uplink Capacity ( Recent Progress in Optoelectronics an
On Dynamic Fault Tolerance for WSI Networks
On Two-Directional Orthogonal Ray Graphs
Orthogonal ray graphs and nano-PLA design (コンカレント工学)
Orthogonal ray graphs and nano-PLA design (回路とシステム)
On Orthogonal Ray Graphs with Applications to NanoPLA Design : Extended Abstract
On Orthogonal Ray Graphs with Applications to NanoPLA Design : Extended Abstract
On Orthogonal Ray Graphs with Applications to NanoPLA Design : Extended Abstract
On the permutation routing in all-optical caterpillar networks (回路とシステム)
On the permutation routing in all-optical caterpillar networks (コンカレント工学)
On the Complexity of Three-Dimensional Orthogonal Face Routing
On the complexity of three-dimensional orthogonal face routing (回路とシステム)
On the Three-Dimensional Orthogonal Drawing of Series-Parallel Graphs
A-1-27 On the Three-Dimensional Layout of Butterfly Networks
A-1-31 A Note on Sparse Networks Tolerating Random Faults for Cycles(A-1. 回路とシステム, 基礎・境界)
On the Proper-Path-Decomposition of Trees
Fault-Tolerant Graphs for Hypercubes and Tori (Special Issue on Architectures, Algorithms and Networks for Massively parallel Computing)
Midblastula transition (MBT) of the cell cycles in the yolk and pigment granule-free translucent blastomeres obtained from centrifuged Xenopus embryos
ESTABLISHMENT A METHOD TO ANALYZE CELL CYCLE AND CELL DIFFERENTIATION UPON EARLY XENOPUS DEVELOPMENT USING TRANSPARENT BLASTOMERES(Developmental Biology,Abstracts of papers presented at the 75^ Annual Meeting of the Zoological Society of Japan)
CHANGES IN INTRACELLULAR CA^ CONCENTRATION DURING EARLY EMBRYONIC CELL CYCLES IN XENOPUS(Developmental Biology,Abstracts of papers presented at the 76^ Annual Meeting of the Zoological Society of Japan)
THE REGULATING MECHANISM OF CENTROSOME SEPARATION AFTER MID-BLASTULA TRANSITION (MBT) IN XENOPUS EMBRYOS(Developmental Biology,Abstracts of papers presented at the 76^ Annual Meeting of the Zoological Society of Japan)
FUNCTIONAL ANALYSIS OF PTEN AT GASTRULATION OF XENOPUS LAEVIS(Developmental Biology,Abstracts of papers presented at the 76^ Annual Meeting of the Zoological Society of Japan)
FUNCTIONAL ANALYSIS OF PTEN AT GASTRULATION OF XENOPUS LAEVIS(Developmental Biology,Abstracts of papers presented at the 75^ Annual Meeting of the Zoological Society of Japan)
On-Line Multicasting in All-Optical Networks
A-1-25 On Efficient Universal Quantum Circuits
Universal test sets for reversible circuits (コンカレント工学)
Universal test sets for reversible circuits (回路とシステム)
A-1-14 Fault Testing for Linear Reversible Circuits
On Fault Testing for Reversible Circuits
Expression of Matrix Metalloproteinases in Patients With Acute Myocardial Infarction
Fault-Tolerant Meshes with Constant Degree(Selected Papers from the 17th Workshop on Circuits and Systems in Karuizawa)
A Note on the Circuit-switched Fixed Routing in Networks (特集並列処理)
Adsolubilization of Yellow OB and Parsol in Dioctadecyldimethylammonium Chloride Layer on Silica
Fault-Tolerant Meshes with Efficient Layouts
AS-1-2 Lower Bounds for the Height of Three-Dimensional Channel Routing
On Two Problems of Nano-PLA Design
On the energy-aware mapping for NoCs (回路とシステム)
A-1-30 On the Three-Dimensional Single-Active-Layer Routing with Dual Channels
A-1-13 Universal Reversible Circuits
A-1-7 On the Complexity of Three-Dimensional Orthogonal Face Routing
On the Three-Dimensional Orthogonal Drawing of Outerplanar Graphs : Extended Abstract
On the Three-Dimensional Orthogonal Drawing of Outerplanar Graphs : Extended Abstract
On the Three-Dimensional Orthogonal Drawing of Outerplanar Graphs : Extended Abstract
On the three-dimensional single-active-layer routing (回路とシステム)
An Efficient Quantum Addition Circuit : Extended Abstract
An Efficient Quantum Addition Circuit : Extended Abstract
An Efficient Quantum Addition Circuit : Extended Abstract
On the three-dimensional single-active-layer routing (コンカレント工学)
A-1-32 A Note on Fault Testing for Reversible Circuits
Special Section on Discrete Mathematics and Its Applications
Efficient Embeddings of Binary Trees with Bounded Proper Pathwidth into Paths and Grids
The Complexity of Three-Dimensional Channel Routing
AS-1-3 Three-Dimensional Channel Routing is in NP
A-1-30 A Note on the Three-Dimensional Channel Routing(A-1. 回路とシステム, 基礎・境界)
The Complexity of Three-Dimensional Channel Routing
A-1-20 On the Quantum Query Complexity of All-Pairs Shortest Paths
The Complexity of Three-Dimensional Channel Routing
AS-1-4 On the Three-Dimensional Layout of Hypercubes
AS-1-1 The Complexity of Fault Testing for Reversible Circuits
A-7-1 A Note on Universally Ideal Secret-Sharing Schemes
A-1-14 A Note on the Maximum Balanced Biclique Problem
A-1-13 A Note on the Subtree Isomorphism Problem
MSA: mixed stochastic algorithm for placement with larger solution space (VLSI設計技術)
An Improved Simulated Annealing for 3D Packing with Sequence Triple and Quintuple Representations (ディペンダブルコンピューティング)
An Improved Simulated Annealing for 3D Packing with Sequence Triple and Quintuple Representations
A-1-34 On the Complexity of Energy-Aware Mapping for NoCs
On Efficient Universal Quantum Circuits (回路とシステム)
On Efficient Universal Quantum Circuits (システム数理と応用)
On Efficient Universal Quantum Circuits
On Efficient Universal Quantum Circuits
On the Complexity of Energy-Aware Mapping for NoCs
On the Complexity of Energy-Aware Mapping for NoCs
On the Complexity of Energy-Aware Mapping for NoCs (信号処理)
A-1-8 A Note on Two-Directional Orthogonal Ray Graphs
A-1-7 A Note on the Cutwidth of Trees
A-1-6 A Note on the Energy-Aware Mapping for NoCs
On the Complexity of Fault Testing for Reversible Circuits
An Improved Simulated Annealing for 3D Packing with Sequence Triple and Quintuple Representations
A-1-9 The Complexity of the Densest κ-Subgraph Problem for Chordal Bipartite Graphs
A-1-10 Characterizations of Orthogonal Ray Trees
An Improved Simulated Annealing for 3D Packing with Sequence Triple and Quintuple Representations
On Minimum Feedback Vertex Sets in Graphs
On Minimum Feedback Vertex Sets in Graphs
On Minimum Feedback Vertex Sets in Graphs
A Note on the Energy-Aware Mapping for NoCs
A Note on the Energy-Aware Mapping for NoCs
On Minimum Feedback Vertex Sets in Bipartite Graphs and Degree-Constraint Graphs

On Dynamic Fault Tolerance for WSI Networks

スポンサーリンク

概要

著者

関連論文

スポンサーリンク