We develop a characterization for m-fault-tolerant extensions, and for optimal m-fault-tolerant extensions, of a complete multipartite graph. Our formulation shows that this problem is equivalent to an interesting combinatorial problem on the partitioning of integers. This characterization leads to a new procedure for constructing an optimal m-fault-tolerant extension of any complete multipartite graph, for any m/spl ges/0. The proposed procedure is mainly useful when the size of the graph is relatively small, because the search time required is exponential. This exponential search, however, is not always necessary. We prove several necessary conditions that help us, in several cases, to identify some optimal m-fault-tolerant extensions without performing any search.>

Abstract Advances in computer technology have made the construction of complex networks with many processors economically feasible. Because of the complexity of such networks, reliability has become a major concern. In some applications, it is critical that the system must be able to operate correctly despite the presence of certain faults. To achieve this fault‐tolerance capability, some spare processors and interconnection links need to be added. In this case, when some of the basic components of the network fail, their tasks can be dynamically transferred to the spare components and the network can continue to operate. The three main criteria that it is desirable to minimize in a fault‐tolerant design are the number of nodes (processors), the number of edges (links), and the maximum number of connections to a node. Minimizing these attributes is important in practice, as it is unlikely that unbounded increase in the number of nodes, edges, or connections per node would be acceptable in a real design. In this paper, we shall consider this optimization problem when the (nonredundant) network under consideration is organized as a star. We study all possible variations of the problem under the assumption that minimizing nodes has the highest priority.

The authors studied the design of a fault-tolerant extension for a graph G which can survive at most m node failures, and which contains the minimum number of nodes and the fewest possible edges when the nonredundant graph (G) is a complete multipartite graph. After developing a characterization for m-fault-tolerant extensions and for optimal m-fault-tolerant extensions of a complete multipartite graph, this characterization is used to develop a procedure to construct an optimal m-fault-tolerant extension of any complete multipartite graph, for any m>or=0. The procedure is only useful when the size of the graph is relatively small, since the search time required is exponential. Several necessary conditions on any (optimal) m-fault-tolerant extension of a complete multipartite graph are proved. These conditions allow identification of some optimal m-fault-tolerant extensions of several special cases of a complete multipartite graph without performing any search.>

Abstract The advance in VLSI technology and the continuing decline in the cost of computer hardware have made the construction of complex networks with many processors economically feasible. Due to the complexity of such systems, reliability has become a major issue. In some applications, it is critical that the system must be able to operate correctly despite the presence of certain faults. Multiprocessor networks with such capability are called fault‐tolerant networks. These networks increase reliability by replicating some of the basic components, i.e., by including spare processors and interconnection links. The problem that arises naturally is that of minimizing the spare components that are needed to tolerate failure. In this paper, we consider this problem when the network under consideration is organized in the form of a star. The paper describes how to design optimal m ‐FT (m‐fault‐tolerant) graphs with respect to the star configuration, for all values of m ≥ 0.