Constructions of sparse asymmetric connectors with number theoretic methods
Andreas Baltz, Gerold Jäger, Anand Srivastav · Networks · 2005
Abstract 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 = Ω(logN + log2n) Oruç (J Parallet Distributed Comput 1994, 359–366 10 ) gave the presently best (n,N)‐connector with O(N + n · logn) 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