Optimal and near-optimal broadcast in random graphs
Edward R. Scheinerman, John C. Wierman · Discrete Applied Mathematics · 1989
One vertex of a graph has a message which it wishes to disseminate to all the other vertices in a graph. At each discrete time unit, a vertex can transmit a message to one of its neighbors. How long does it take for the message to be broadcast to all other vertices? We show that for sparse random graphs, near-optimal broadcast can be expected and for slightly denser graphs, true optimal broadcast occurs.