PUB - Publikationen an der Universität Bielefeld

An (n, N)-connector of depth d is an acyclic digraph with n inputs and N outputs in which for any injective mapping of input vertices into output vertices there exist n vertex disjoint paths of length at most d joining each input to its corresponding output. In this paper we consider the problem of construction of sparse depth two connectors with n << N. We use posets of star products and their matching properties to construct such connectors. In particular, this gives a simple explicit construction for connectors of size O(N log n/log log n). Thus our earlier idea to use other posets than the family of subsets of a finite set was successful. (c) 2006 Elsevier Inc. All rights reserved.