Lower bounds on communication overlap of networks

From MaRDI portal





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.











This page was built for publication: Lower bounds on communication overlap of networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1095665)