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
    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
    0 references
    0 references
    0 references
    0 references
    interconnection network
    0 references
    communication overlap
    0 references
    0 references
    0 references
    0 references