Three-Stage Generalized Connectors
Richard M. Karp · SIAM Journal on Discrete Mathematics · 1992
An acyclic directed network with n sources and m sinks is called a generalized connector if, for any request pattern in which each sink asks to be connected to some source, the required configuration of noninterfering connecting paths can be set up. This paper presents new families of two- and three-stage connection networks and gives a method of establishing that particular networks in these families are generalized connectors. This method is based on the Erdös probabilistic method and consists of two steps: 1. First it is proven that a given network is a generalized connector provided that certain events in a probability space $\Omega $ are of sufficiently low probability. 2. Then it is shown that the probabilities of these events are indeed sufficiently small.For the family of designs presented in Section 5, the second step is accomplished by explicitly calculating the probabilities of the events in question, using dynamic programming; these calculations provide rigorous proofs that the designs are correct. However, for the more economical designs of Section 6, the probabilities of the events in question are not calculated exactly, but instead are estimated by drawing pseudo-random samples from the probability space $\Omega $. Thus, we have only a “statistical proof” (albeit a very convincing one) of the correctness of these designs. For certain choices of n and m the most efficient three-stage generalized connectors currently known are obtained.