Rearrangeable networks are switching systems capable of establishing simultaneous independent communication paths in accordance with any one-to-one correspondence between their n inputs and n outputs. Classical results show that Ω( n log n ) switches are necessary and that O( n log n ) switches are sufficient for such networks. We are interested in the minimum possible number of switches in rearrangeable networks in which the depth (the length of the longest path from an input to an output) is at most k, where k is fixed as n increases. We show that Ω( n1 + 1/k ) switches are necessary and that O( n1 + 1/k ( log n )1/k ) switches are sufficient for such networks.
© 1982 Society for Industrial and Applied Mathematics
Pippenger, Nicholas, and Andrew C.-C. Yao. “Rearrangeable Networks with Limited Depth.” SIAM Journal on Algebraic and Discrete Methods 3, no. 4 (December 1982): 411-417.