Broadcasting in random graphs
The broadcast problem is, given a graph \(G = (V,E)\) and a starting vertex \(v \in V\) that holds a piece \(i\) of information, to distribute \(i\) to all vertices. It is assumed, that at each time step any vertex knowing \(i\) can share it with at most one of its neighbours. A graph has property \(\mathcal B\) if it is possible to distribute a piece of information in \(\lceil \log_ 2 n\rceil\) time steps from everu possible starting vertex. The authors investigate the probability that a random graph \(G_{n,p}\) with edge density \(p\) has property \(\mathcal B\). Improving older upper bounds they show that there exists a constant \(c > 0\) (\(c = 18\) will work) such that if \(p \geq (c \ln n)/n\) then \(G_{n,p}\) has property \(\mathcal B\) with high probability (i.e. with probability \(1 - o(1)\) as \(n \to \infty\)).
- Broadcasting in DMA-bound bounded degree graphs
- Perfect broadcasting in unlabeled networks
- Voronoi-like nondeterministic partition of a lattice by collectives of finite automata
- On linear-time data dissemination in dynamic rooted trees
- Close-to-optimal and near-optimal broadcasting in random graphs
- Probabilistic flooding for efficient information dissemination in random graph topologies
- The unit acquisition number of binomial random graphs
- The role of randomness in the broadcast congested clique model
- The total acquisition number of random geometric graphs
- Radio communication in random graphs
- Broadcasts in graphs
- The total acquisition number of random graphs
- Randomized broadcast in networks
- On Radio Broadcasting in Random Geometric Graphs
- Broadcasting in Bounded Degree Graphs
- scientific article; zbMATH DE number 1792638 (Why is no real title available?)
- The worst case behavior of randomized gossip protocols
- Broadcasting on Random Directed Acyclic Graphs
- scientific article; zbMATH DE number 6297797 (Why is no real title available?)
- Constrained information transmission on Erdős-Rényi graphs
- Efficient randomised broadcasting in random regular networks with applications in peer-to-peer systems
- Broadcasting in random graphs
- Bounds on broadcast time in well-connected graphs
- Agent-based randomized broadcasting in large networks
- Optimal and near-optimal broadcast in random graphs
This page was built for publication: Broadcasting in random graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5906597)
