The Cover Time of Random Digraphs.

Authors :: Hutchison, David
Kanade, Takeo
Kittler, Josef
Kleinberg, Jon M.
Mattern, Friedemann
Mitchell, John C.
Naor, Moni
Nierstrasz, Oscar
Pandu Rangan, C.
Steffen, Bernhard
Sudan, Madhu
Terzopoulos, Demetri
Tygar, Doug
Vardi, Moshe Y.
Weikum, Gerhard
Charikar, Moses
Jansen, Klaus
Reingold, Omer
Rolim, José D. P.
Cooper, Colin
Source :: Approximation, Randomization & Combinatorial Optimization. Algorithms & Techniques (9783540742074); 2007, p422-435, 14p
Publication Year :: 2007
Abstract: We study the cover time of a random walk on the random digraph Dn,p when $p=\frac{d\log n}{n}, d>1$. We prove that whp the cover time is asymptotic to . [ABSTRACT FROM AUTHOR]

Language :: English
ISBNs :: 9783540742074
Database :: Complementary Index
Journal :: Approximation, Randomization & Combinatorial Optimization. Algorithms & Techniques (9783540742074)
Publication Type :: Book
Accession number :: 33421228
Full Text :: https://doi.org/10.1007/978-3-540-74208-1_31