Random broadcast on random geometric graphs

摘要: In this work, we consider the random broadcast time on geometric graphs (RGGs). The classic model, also known as push algorithm, is defined as: starting with one informed node, in each succeeding round every node chooses of its neighbors uniformly at and informs it. We RGGs, when high probability: (i) RGG connected, (ii) there exists giant component RGG. show that bounded by {Omicron}({radical} n + diam(component)), where diam(component) a diameter entire graph, or component, for regimes (i), (ii), respectively. other words, both regimes, derive to be {Theta}(diam(G)), which asymptotically optimal.