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

AbstractBroadcasting 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 Gn,p random graphs. We prove here that in Gn,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 nn, for any constant c > 16, a message held by any vertex of a Gn,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