Superconcentrators

Abstract

An n-superconcentrator is an acyclic directed graph with n inputs and n outputs for which, for every $r \leqq n$, every set of r inputs, and every set of r outputs, there exists an r-flow (a set of r vertex-disjoint directed paths) from the given inputs to the given outputs. We show that there exist n-superconcentrators with $39n + O(\log n)$ (in fact, at most $40n$) edges, depth $O(\log n)$, and maximum degree (in-degree plus out-degree) 16.