Premium
The cover time of sparse random graphs
Author(s) -
Cooper Colin,
Frieze Alan
Publication year - 2006
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20151
Subject(s) - cover (algebra) , struct , combinatorics , mathematics , random graph , binary logarithm , random walk , discrete mathematics , statistics , computer science , graph , engineering , mechanical engineering , programming language
We study the cover time of a random walk on graphs G ∈ G n , p when $p={c\log n \over n}, c>1$ . We prove that whp , the cover time, is asymptotic to $c\log({c \over c-1})n\log n$ . © 2006 Wiley Periodicals, Inc. Random Struct. Alg., 2007
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom