##### Department of Mathematics,

University of California San Diego

****************************

### Math 269 - Combinatorics

## Robert Elsaesser

#### UCSD Postdoc

## Radio communication in random graphs

##### Abstract:

One of the most frequently studied problems in the context of information dissemination in communication networks is the broadcasting problem. We propose here several time efficient, centralized as well as fully distributed procedures for the broadcasting problem in random radio networks. In particular we show how to perform a centralized broadcast in a random graph $G_p=(V,E)$ of size $n=|V|$ and expected average degree $d=pn$ in time $O(\ln n/\ln d+\ln d).$ Later we present a randomized distributed broadcasting algorithm with the running time $O(\ln n).$ In both cases we show that the presented algorithms are asymptotically optimal by deriving lower bounds on the complexity of radio broadcasting in random graphs. In these proofs we determine some structural properties in random graphs which may be of independent interest. We should note here that the results of this paper hold with probability $1-o(1/n)$. This is a joint work with Leszek Gasieniec from the University of Liverpool.

Host:

### May 10, 2005

### 4:00 PM

### AP&M 7321

****************************