Optimal fault-tolerant networks with a server

Fast computation through parallel processing and large distributed memory are two important qualities of new multiprocessor computing machines. Various processors of these machines are interconnected through a suitable network. However, a fault in a single processor may drastically reduce the performance rate of these machines. Hence, the designing aspects of fault-tolerant networks have received much attention in recent years. A network N′ with n + k processors is called a k-fault-tolerant network with respect to a target network N with n processors if every truncated network of N′ with k faulty processors retains the network of N. A processor in a network which is connected to all other processors is called a server. In this paper, we characterize the k-fault-tolerant networks when the target network contains a server. © 2000 John Wiley & Sons, Inc.