Abstract
This article deals with the design of networks to be placed on satellites. These networks should connect inputs (corresponding to signals arriving at the satellite) to outputs (corresponding to amplifiers, also called Traveling Wave Tube Amplifiers (TWTA)), even in case of failures of amplifiers. The networks are made of links and expensive switches; hence, we want to minimize the number of switches subject to the following conditions: Each input and each output is connected to exactly one switch; each switch is adjacent to exactly four links; there are n inputs and n + k outputs; among the n + k outputs, k can fail permanently; and, finally, all the input signals should be sent to valid amplifiers, that is, outputs, via disjoint paths. So, the aim is to design networks having as few switches as possible and satisfying the following property: There exist n edgeβdisjoint paths from the n inputs to any set of n outputs chosen from the n + k total number of outputs. We call such networks valid kβfault tolerant networks. Let π©(n, k) denote the minimum number of switches of a valid network with n inputs, n + k outputs, and k output failures. In this article, we give some details on the problem and some preliminary results such as the fact that π©(n, k) β₯ n. We also propose a general construction which yields (under some conditions) π©(n + nβ², k) β€ π©(n, k) + π©(nβ², k). Β© 2002 Wiley Periodicals, Inc.