DIMACS TR: 97-12

Threshold of Broadcast in Random Graphs

Author: Hui Chen


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