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 -