On Concentrators, Superconcentrators, Generalizers, and Nonblocking Networks

A communication network can be viewed as a collection of vertices and edges which provides connection between input vertices and output vertices by nonintersecting (vertex-disjoint) paths. Various types of communication networks, such as concentrators, superconcentrators, generalizers, and rearrangeable and nonblocking networks, have been extensively studied 18 and can be used to build efficient switching networks or to serve as useful tools for complexity theory for algorithms. 8 An (n, m)-concentrator is a graph with n input vertices and m output vertices, n > m, having the property that, for any set of m or fewer inputs, a set of vertex-disjoint paths exists that join the given inputs in a one-to-one fashion to different outputs. If this graph is directed or acyclic, we call it a directed or acyclic (ft, m)-concentrator, respectively. Pinsker 4 shows the existence of a directed acyclic (ft, m)-concentrator with 29ft edges. We show that there exist (ft, m)-concentrators with 15ft edges, there exist directed (ft, m)-concentrators with about 25ft edges, and there exist directed acyclic (ft, m)-concentrators with 27n edges. An ft-superconcentrator is a graph with n inputs and n outputs having the property that, for any set of inputs and any equinumerous set of outputs, a set of vertex-disjoint paths exists that join the given inputs in a one-to-one fashion to the given outputs. Valiant 9 shows the existence of directed acyclic ft-superconcentrators with 238ft edges. 1765