Rearrangeable Networks with Limited Depth
Nicholas J. Pippenger, Andrew Chi-Chih Yao · SIAM Journal on Algebraic and Discrete Methods · 1982
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 $\Omega ( 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 $\Omega ( n^{1 + 1/k} )$ switches are necessary and that $O ( n^{1 + 1/k} ( \log n )^{1/k} )$ switches are sufficient for such networks.