Rearrangeable Networks with Limited Depth

Authors

Nicholas Pippenger, Harvey Mudd CollegeFollow
Andrew C.-C. Yao, University of California - Berkeley

Document Type

Article

Department

Mathematics (HMC)

Publication Date

1982

Abstract

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 Ω( n^{1 + 1/k} ) switches are necessary and that O( n^{1 + 1/k} ( log n )^1/k ) switches are sufficient for such networks.

Rights Information

© 1982 Society for Industrial and Applied Mathematics

Recommended Citation

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.