clarke@csri.toronto.edu (Jim Clarke) (02/23/88)
THEORY SEMINAR, Thursday, February 25, 3 pm, GB244
(GB = Galbraith Building, 35 St. George Street)
Dr. Anna Karlin
Princeton University
"Bounds on Covering Times"
Consider a particle moving on a connected, undirected graph on n vertices,
choosing uniformly at random to move to one of the vertices neighboring on
it's current position. The covering time is the time it takes until the
particle has visited all the vertices in the graph, starting from an arbi-
trary vertex.
In this talk, we present upper and lower bounds on the expected covering
time for graphs in terms of the eigenvalues of the corresponding Markov
chain. A consequence of these bounds is that regular expander graphs have
expected covering time Theta(n log n). The techniques also yield an
improved bound on the length of universal sequences for expanders.
(This is joint work with Andrei Broder of DEC SRC.)
--
Jim Clarke -- Dept. of Computer Science, Univ. of Toronto, Canada M5S 1A4
(416) 978-4058
BITNET,CSNET: clarke@csri.toronto.edu CDNNET: clarke@csri.toronto.cdn
UUCP: {allegra,cornell,decvax,linus,utzoo}!utcsri!clarke