DOE OSTI · 988313
Random broadcast on random geometric graphs
Abstract
In this work, we consider the random broadcast time on random geometric graphs (RGGs). The classic random broadcast model, also known as push algorithm, is defined as: starting with one informed node, in each succeeding round every informed node chooses one of its neighbors uniformly at random and informs it. We consider the random broadcast time on RGGs, when with high probability: (i) RGG is connected, (ii) when there exists the giant component in RGG. We show that the random broadcast time is bounded by {Omicron}({radical} n + diam(component)), where diam(component) is a diameter of the entire graph, or the giant component, for the regimes (i), or (ii), respectively. In other words, for both regimes, we derive the broadcast time to be {Theta}(diam(G)), which is asymptotically optimal.
Explore related subjects
Keep this discovery
Explore connections, maps & timelines
Bradonjic, Milan, Elsasser, Robert, Friedrich, Tobias, Sauerwald, Tomas. 2009-01-01. Random broadcast on random geometric graphs. https://www.osti.gov/biblio/988313
Cite the original work for its findings. Save a collection to share your selection of sources.