Close-to-optimal and near-optimal broadcasting in random graphs

Broadcasting in random graphs has drawn increasing attention in the past years. Various results have been previously shown related to the minimum time needed to broadcast a message from any vertex to all the vertices of G_n,p random graphs. We prove here that in G_n,p random graphs for the value of probability p used in Gerbessiotis, near-optimal broadcast can be achieved, with high probability, in llg n + O(lg lg lg n) time steps, an improvement over the previous time bound of lg n + O(lg lg n). It is assumed that at any time step a given vertex could either transmit to or receive from at most one other vertex one message in unit time. We also prove that for p = c lg lg lg n log n n, for any constant c > 16, a message held by any vertex of a G_n,p random graph can be broadcast to all other vertices in at most lgn + 1 time steps, with high probability. Both proofs use techniques from the works of Gerbessiotis, and Scheinerman and Wierman (1989) as well as new ones that allow the new results to be obtained.