A lower bound on strictly non-blocking networks

Abstract

We prove that a strictly non-blocking n-connector of depth k must have ω(n1+1/(k-1)) edges. © 1988 Akadémiai Kiadó.