Lower bounds on communication overlap of networks
From MaRDI portal
(Redirected from Lower bounds on communication overlap of networks)
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.
Recommendations
Cites work
Cited in
(8)- New lower and upper bounds for the competitive ratio of transmission protocols
- Bounded-hop communication networks
- Lower bounds for merging networks
- Message Lower Bounds via Efficient Network Synchronization
- The minimum geodetic communication overlap graphs
- On the structure of minimum communication overlap networks
- Tight Network Topology Dependent Bounds on Rounds of Communication
- Some lower bounds in dynamic networks with oblivious adversaries
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)