This article is cited in 7 papers

Technical Diagnostics

Minimized embedding of arbitrary hamiltonian graphs in fault-tolerant graph and reconfiguration at faults. II. Grids and $k$-fault-tolerance

M. F. Karavai

Trapeznikov Institute of Control Sciences, Russian Academy of Sciences, Moscow, Russia

Abstract: Optimal algorithms to construct 1-fault-tolerant structures were presented with examples of simple and diagonal grids and torus based on algorithm A2 discussed in the first part of the paper. The general procedure of constructing the $k$-fault-tolerant structures was presented first for a simple cycle and then for more involved grid graphs. Algorithms for reconfiguration after failure were described. For the 1-fault-tolerant structures, these algorithms are realized as a simple table of automorphisms of the fault-tolerant graph. For the case of $k$-fault-tolerance, correct reconfiguration requires symmetrization of the reduced graph after the $i$th failure by elimination of the redundant connections introduced to improve fault-tolerance from $i-1$ to $i$ when constructin the $k$-fault-tolerant system graph.

Presented by the member of Editorial Board: P. P. Parkhomenko

Received: 05.02.2004

 English version: Automation and Remote Control, 2005, 66:2, 328–340

Bibliographic databases:

• 
• 
•