On synchronous strictly non-blocking concentrators and generalized-concentrators

The optimal bound of (n-m+c)c+(m-c) and an Ω(k(n-m+c)c^1/k ) lower bound on the size of synchronous strictly non-blocking c-limited (n,m)-concentrators with depth 1 and depth k respectively are proved. A consequence of the lower-bound result is an Θ(n^1+1/k) bound on the size of synchronous strictly non-blocking fixed ratio γn -limited (αn,βn)-concentrators (γ<β) with constant depth k. For synchronous strictly non-blocking (c,r)-limited (n,m )-generalized-concentrators, the optimal size of nc-[^m-c/_r](c-r) for depth 1 and a lower bound size-depth tradeoff Ω((n-^m /_r+^c/_r)r^k-1/k c^1/k) for constant depth k and r= o(c) are also presented