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 ≤ N ) by as few edges as possible such that for every injective mapping f : I → O there are n vertex disjoint paths from i to f ( i ) of length k for a given k ∈ IN. For k = Ω(log N + log 2 n ) Oruç (J Parallet Distributed Comput 1994, 359–36610) 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\lceil\sqrt{n + 5/4} - 1/2\rceil + n\lceil\sqrt{n + 5/4} - 1/2 \rceil \sqrt{N}$ edges. We show by a probabilistic argument that an optimal ( n , N )‐connector has Θ( N ) edges, if n ≤ N ½−ε for some ∈ ≥ 0. Moreover, we give explicit constructions based on a new number theoretic approach that need at most $N\lceil \sqrt{3n/4}\rceil + 2n\lceil \sqrt {3n/4}\rceil\lceil\sqrt{N}\rceil$ edges for arbitrary choices of n and N . The improvement we achieve is based on applying a generalization of the Erdős‐Heilbronn conjecture on the size of restricted sums. © 2005 Wiley Periodicals, Inc. NETWORKS, Vol. 45(3), 119–124 2005