Gavriela Freund Lev, Leslie G. Valiant, et al.
IEEE TC
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 least 3n log3n - O(n) contacts where n is the number of connections to be established simultaneously. Copyright © 1974 by The Institute of Electrical and Electronics Engineers, Inc.
Gavriela Freund Lev, Leslie G. Valiant, et al.
IEEE TC
Yossi Azar, Nicholas Pippenger
Discrete Applied Mathematics
Nicholas Pippenger
Mathematical Systems Theory
Ronald Fagin, Jurg Nievergelt, et al.
ACM Transactions on Database Systems (TODS)