TY - JOUR

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

AU - Gerbessiotis, Alexandros V.

N1 - Funding Information:
’ Research supported in part by NSF grants NSF-CCR-89-02500 and NSF-CCR-9200884. Present address: 97 Gr. Kousidou St., Zografou, Athens 15772, Greece.

PY - 1995/11/17

Y1 - 1995/11/17

N2 - 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 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 n n, 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.

AB - 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 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 n n, 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.

UR - http://www.scopus.com/inward/record.url?scp=0038927695&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0038927695&partnerID=8YFLogxK

U2 - 10.1016/0166-218X(95)00004-B

DO - 10.1016/0166-218X(95)00004-B

M3 - Article

AN - SCOPUS:0038927695

VL - 63

SP - 129

EP - 150

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

SN - 0166-218X

IS - 2

ER -