The cover time of sparse random graphs

被引：44
作者：
Cooper, Colin
Frieze, Alan [1 ]
机构：
[1] Carnegie Mellon Univ, Dept Math Sci, Pittsburgh, PA 15213 USA
[2] Univ London Goldsmiths Coll, Dept Math & Comp Sci, London SW14 6NW, England
来源：
RANDOM STRUCTURES & ALGORITHMS | 2007年 / 30卷 / 1-2期
关键词：
random walk; random graphs; cover time;
D O I：
10.1002/rsa.20151
中图分类号：
TP31 [计算机软件];
学科分类号：
081202 ; 0835 ;
摘要：
We study the cover time of a random walk on graphs G epsilon G(n,p), when p = c log n /n, c > 1. We prove that whp, the cover time, is asymptotic to c log (c/c-1) n log n. (c) 2006 Wiley Periodicals, Inc.
引用
收藏
页码：1 / 16
页数：16
相关论文
共 50 条
  • [21] ON THE COVER TIME OF DENSE GRAPHS
    Cooper, Colin
    Frieze, Alan M.
    Pegden, Wesley
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 2019, 33 (03) : 1374 - 1389
  • [22] Twin-width of sparse random graphs
    Hendrey, Kevin
    Norin, Sergey
    Steiner, Raphael
    Turcotte, Jeremie
    COMBINATORICS PROBABILITY AND COMPUTING, 2024,
  • [23] ON THE GAME CHROMATIC NUMBER OF SPARSE RANDOM GRAPHS
    Frieze, Alan
    Haber, Simcha
    Lavrov, Mikhail
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 2013, 27 (02) : 768 - 790
  • [24] First order distinguishability of sparse random graphs
    Hershko, Tal
    Zhukovskii, Maksim
    PROCEEDINGS OF THE 39TH ANNUAL ACM/IEEE SYMPOSIUM ON LOGIC IN COMPUTER SCIENCE, LICS 2024, 2024,
  • [25] Sparse graphs using exchangeable random measures
    Caron, Francois
    Fox, Emily B.
    JOURNAL OF THE ROYAL STATISTICAL SOCIETY SERIES B-STATISTICAL METHODOLOGY, 2017, 79 (05) : 1295 - 1366
  • [26] PLANARITY AND GENUS OF SPARSE RANDOM BIPARTITE GRAPHS
    Do T.A.
    Erde J.
    Kang M.
    SIAM Journal on Discrete Mathematics, 2022, 36 (02) : 1394 - 1415
  • [27] On the max-cut of sparse random graphs
    Gamarnik, David
    Li, Quan
    RANDOM STRUCTURES & ALGORITHMS, 2018, 52 (02) : 219 - 262
  • [28] ON THE NUMBER OF HAMILTON CYCLES IN SPARSE RANDOM GRAPHS
    Glebov, Roman
    Krivelevich, Michael
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 2013, 27 (01) : 27 - 42
  • [29] Comparing mixing times on sparse random graphs
    Ben-Hamou, Anna
    Lubetzky, Eyal
    Peres, Yuval
    ANNALES DE L INSTITUT HENRI POINCARE-PROBABILITES ET STATISTIQUES, 2019, 55 (02): : 1116 - 1130
  • [30] First return times on sparse random graphs
    Evnin, Oleg
    Horinouchi, Weerawit
    JOURNAL OF PHYSICS A-MATHEMATICAL AND THEORETICAL, 2025, 58 (07)
12345