[Colloq] Greg Plaxton, Monday, April, 10, 10:30am

[Rachel Kalweit]

College of Computer and Information Science Colloquium

Presents:
Greg Plaxton
University of Texas at Austin

Who will speak on:
Optimal Cover Time for a Graph-Based Coupon Collector Process

Monday, April 10, 2006
10:30am
366 West Village H
Northeastern University


Abstract:
In this talk we study the following covering process defined over an 
arbitrary directed graph. Each node is initially uncovered and is 
assigned a random integer rank drawn from a suitable range. The process 
then proceeds in rounds. In each round, a uniformly random node is 
selected and its lowest-ranked uncovered outgoing neighbor, if any, is 
covered. We prove that if each node has in-degree $\Theta(d)$ and 
out-degree $O(d)$, then with high probability, every node is covered 
within $O(n+\frac{n\log n}{d})$ rounds, matching a lower bound due to 
Alon. Alon has also shown that, for a certain class of $d$-regular 
expander graphs, the upper bound holds no matter what method is used to 
choose the uncovered neighbor. In contrast, we show that for arbitrary 
$d$-regular graphs, the method used to choose the uncovered neighbor can 
affect the cover time by more than a constant factor.

Joint work with Ned Dimitrov.

Host: Ravi Sundaram