TY - JOUR

T1 - Broadcasting in random graphs

AU - Gerbessiotis, Alexandros V.

N1 - Funding Information:
*Corresponding author. ‘Supported in part by NSF grants CCR9024935 and CCR9225008. ‘Supported in part by NSF grant CCR9225008. 3An event E. is said to occur whp (with high probability) if Pr(e,)

PY - 1994/9/14

Y1 - 1994/9/14

N2 - One of the major problems that have arisen in communication networks is that of broadcasting, namely the dissemination of a message possessed initially by a given vertex to all the vertices of a network. It is assumed that at any time step a given vertex can transmit to or receive from some other vertex exactly one message. We are interested in the minimum time needed to broadcast a message from one vertex to all the vertices of Gn,p random graphs. We are also interested in the broadcast number of such graphs. The problem of broadcasting in random graphs was studied by Scheinerman and Wierman in (1989), where they proved that it was possible to perform, with high probability, near-optimal broadcast in Gn,p random graphs for p=ωnlog n n with ωn→∞ as n→∞. They also proved that, for a given algorithm, it was possible, with probability, to optimally broadcast a message from any given vertex to all the vertices of Gn,p random graphs with edge probability p=c log2 n n, for a properly chosen constant c, in exactly ⌈lgn⌉ time steps. We prove here results related to two conjectures posed by them regarding the optimality of the edge probabilities they used in their paper.

AB - One of the major problems that have arisen in communication networks is that of broadcasting, namely the dissemination of a message possessed initially by a given vertex to all the vertices of a network. It is assumed that at any time step a given vertex can transmit to or receive from some other vertex exactly one message. We are interested in the minimum time needed to broadcast a message from one vertex to all the vertices of Gn,p random graphs. We are also interested in the broadcast number of such graphs. The problem of broadcasting in random graphs was studied by Scheinerman and Wierman in (1989), where they proved that it was possible to perform, with high probability, near-optimal broadcast in Gn,p random graphs for p=ωnlog n n with ωn→∞ as n→∞. They also proved that, for a given algorithm, it was possible, with probability, to optimally broadcast a message from any given vertex to all the vertices of Gn,p random graphs with edge probability p=c log2 n n, for a properly chosen constant c, in exactly ⌈lgn⌉ time steps. We prove here results related to two conjectures posed by them regarding the optimality of the edge probabilities they used in their paper.

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

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

U2 - 10.1016/0166-218X(94)90182-1

DO - 10.1016/0166-218X(94)90182-1

M3 - Article

AN - SCOPUS:0040705621

VL - 53

SP - 149

EP - 170

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

SN - 0166-218X

IS - 1-3

ER -