Lower bounds on communication overlap of networks (Q1095665)

For an interconnection network, we introduce a graph-theoretical invariant called communication overlap - the number of paths passing through the most crowded node under the best communication arrangement in the network when each pair of nodes needs a path to communicate with each other. Further, we establish tight lower bounds for several kinds of networks. For an n-node general network with average fan-out r, we obtain \(\Omega\) (n log n/log r) as its tight lower bound of communication overlap.