Superconcentrators of depths 2 and 3; odd levels help (rarely)

摘要

It is shown that the minimum possible number of edges in an n-superconcentrator of depth 3 is Θ(n log log n), whereas the minimum possible number of edges in an n-superconcentrator of depth 2 is Ω(n(log n)3/2) (and is O(n(log n)2)).