Constructions of sparse asymmetric connectors with number theoretic methods
We consider the problem of connecting a set 1 of n inputs to a set O of N outputs (n   O there are n vertex disjoint paths from i to f(i) of length k for a given k epsilon IN. For k = Omega (log N + log(2) n) Oruc (J Parallet Distributed Comput 1994,359-366 [10]) gave the presently best (n, N)-connector with O(N+ n - log n) edges. For k = 2 and N the square of a prime, Richards and Hwang (1985) described a construction using N [root n + 5/4 - 1/2] + n[ root n + 5/4 - 1/2] root N edges. We show by a probabilistic argument that an optimal (n,N)-connector has Theta(N) edges, if n   0. Moreover, we give explicit constructions based on a new number theoretic approach that need at most N[root 3n/4] + 2n[root 3n/4n] [root N] edges for arbitrary choices of n and N. The improvement we achieve is based on applying a generalization of the Erdos-Heilbronn conjecture on the size of restricted sums. (c) 2005 Wiley Periodicals, Inc.
connector restricted sums rearrangeable network sparse switch permuter combinatorial number theory