On the Complexity of Strictly Nonblocking Concentration Networks

Authors

Nicholas Pippenger, Harvey Mudd CollegeFollow

Document Type

Article

Department

Mathematics (HMC)

Publication Date

1974

Abstract

A concentration network is a contact switching network that provides a number of potential users (connected to its inputs) with access to a smaller number of equivalent resources (connected to its outputs). Its basic property is that any sufficiently small subset of the inputs can be simultaneously connected by disjoint paths to distinct outputs, although the particular outputs to which they are to be connected cannot, in general, be specified arbitrarily. We show that a strictly nonblocking concentration network must have at least3n log_{3} n - O(n)contacts wherenis the number of connections to be established simultaneously.

Rights Information

© 1974 Elsevier Ltd.

Terms of Use & License Information

Terms of Use for work posted in Scholarship@Claremont.

DOI

10.1109/TCOM.1974.1092121

Recommended Citation

Pippenger, N., "On the Complexity of Strictly Nonblocking Concentration Networks," Communications, IEEE Transactions on , vol.22, no.11, pp.1890,1892, Nov 1974 doi: 10.1109/TCOM.1974.1092121