DIMACS TR: 97-12
Threshold of Broadcast in Random Graphs
Author: Hui Chen
ABSTRACT
Broadcasting process is to send a piece of information which resides at one nodein the graph to all the remaining nodes. At each time step, a node
knows about the information can send it to one of its neighbors. The
broadcast problem is to find the minimum time step needed. The problem
is NP hard in general. For a random graph $G_{n,p}$, we are interested
in at what value of $p$ there exists a broadcast tree of depth exactly
$\lc \log _2n\rc $. Frieze and Molloy \cite{FriMo} show that $p$ is of
magnitude $\Theta ( \ln n/n)$. In this paper, we give the exact threshold of theedge probability for the existence of such a tree.
Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1997/97-12.ps.gz
DIMACS Home Page