Constructions of Sparse Asymmetric Connectors

摘要

We consider the problem of connecting a set I of n inputs to a set O of N outputs (n ≤ N) by as few edges as possible, such that for each injective mapping f : I → O there are n vertex disjoint paths from i to f(i) of length k for a given k ∈ N. For k = Ω(log N + log~2 n) Oruc. gave the presently best (n, N)-connector with O(N + n ·log n) edges. For k = 2 we show by a probabilistic argument that an optimal (n, N)-connector has Θ(N) edges, if n ≤ N1/2-ε for some ε> 0. Moreover, we give explicit constructions based on a new number theoretic approach that need O(Nn1/2 + N1/2 n3/2) edges.