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

Research output: Contribution to journalArticlepeer-review

3 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)129-150
Number of pages22
JournalDiscrete Applied Mathematics
Volume63
Issue number2
DOIs
StatePublished - Nov 17 1995
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Close-to-optimal and near-optimal broadcasting in random graphs'. Together they form a unique fingerprint.

Cite this