Lower bounds on communication overlap of networks (Q1095665)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Lower bounds on communication overlap of networks |
scientific article |
Statements
Lower bounds on communication overlap of networks (English)
0 references
1986
0 references
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.
0 references
interconnection network
0 references
communication overlap
0 references