Document Type
Article
Department
Mathematics (HMC)
Publication Date
1977
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.
Rights Information
© 1977 Society for Industrial and Applied Mathematics
Recommended Citation
Pippenger, Nicholas. “Superconcentrators.” SIAM Journal on Computing 6, no. 2 (June 1977): 298-304.
