Optimal and near-optimal broadcast in random graphs
type: Item
instance of: scholarly article
title: Optimal and near-optimal broadcast in random graphs
zbMATH Open document ID: 0709.05031
DOI: 10.1016/0166-218X(89)90007-3
author: Edward Scheinerman
author: John C. Wierman
published in: Discrete Applied Mathematics
publication date: 1989-01-01T00:00:00Z
review text: One vertex of a graph has a message which it wishes to transmit to all other vertices. At each discrete time unit, a vertex can send the message to one of its neighbours. Writing \(b_ v\) for the minimum time necessary for a message originating at v to reach all other vertices, the broadcast number \(b=\max_{v}b_ v\). Call a graph on n vertices broadcast optimal if \(b=\lceil \log_ 2n\rceil\). Consider the graph G on n vertices, each pair of which is joined by an edge with probability \(p_ n\). It is shown that, with large probability, G is broadcast optimal if \(p_ n=c(\log n)^ 2n\) where c is sufficiently large, and `near optimal' if \(p_ n=w_ n\) log n/n where \(w_ n\to \infty\) and \(n\to \infty\); `near optimal' means that \(b=\lceil \log_ 2n\rceil (1+o(1))\) as \(n\to \infty\). Certain conjectures are made for the case \(p_ n=\alpha\log n/n.\)
Mathematics Subject Classification ID: 05C80
zbMATH DE Number: 4164909
zbMATH Keywords: random graph
zbMATH Keywords: broadcast number
reviewed by: G. R. Grimmett
MaRDI profile type: Publication
cites work: Q3682518
cites work: Q3267900
cites work: Q3286850
cites work: Minimum broadcast graphs
cites work: Graphs and matching theorems
full work available at URL: 0166-218x(89)90007-3
OpenAlex ID: W2028402123
Recommended article: Close-to-optimal and near-optimal broadcasting in random graphs
Recommended article: Broadcasting in random graphs
Recommended article: Q5417718
Recommended article: Optimum Broadcasting in Complete Weighted-Vertex Graphs
Recommended article: Broadcasting on Random Directed Acyclic Graphs
Recommended article: Efficient randomised broadcasting in random regular networks with applications in peer-to-peer systems
description: scientific article; zbMATH DE number 4164909