The cover time of the giant component of a random graph

被引：39
作者：
Cooper, Colin [2 ]
Frieze, Alan [1 ]
机构：
[1] Carnegie Mellon Univ, Dept Math Sci, Pittsburgh, PA 15213 USA
[2] Kings Coll London, Dept Comp Sci, London WC2R 2LS, England
来源：
RANDOM STRUCTURES & ALGORITHMS | 2008年 / 32卷 / 04期
关键词：
cover time; random graphs; giant component;
D O I：
10.1002/rsa.20201
中图分类号：
TP31 [计算机软件];
学科分类号：
081202 ; 0835 ;
摘要：
We study the cover time of a random walk on the largest component of the random graph G(n,p). We determine its value up to a factor 1 + o(1) whenever np = c > 1, c = O(ln n). In particular, we show that the cover time is not monotone for c = Theta(ln n). We also determine the cover time of the k-cores, k >= 2. (c) 2008 Wiley Periodicals, Inc.
引用
收藏
页码：401 / 439
页数：39
相关论文
共 50 条
  • [1] The Cover Time of the Giant Component of a Random Graph (vol 32, pg 401, 2008)
    Cooper, Colin
    Frieze, Alan
    RANDOM STRUCTURES & ALGORITHMS, 2009, 34 (02) : 300 - 304
  • [2] The Mixing Time of the Giant Component of a Random Graph
    Benjamini, Itai
    Kozma, Gady
    Wormald, Nicholas
    RANDOM STRUCTURES & ALGORITHMS, 2014, 45 (03) : 383 - 407
  • [3] Anatomy of a Young Giant Component in the Random Graph
    Ding, Jian
    Kim, Jeong Han
    Lubetzky, Eyal
    Peres, Yuval
    RANDOM STRUCTURES & ALGORITHMS, 2011, 39 (02) : 139 - 178
  • [4] Cover time of a random graph with given degree sequence
    Abdullah, Mohammed
    Cooper, Colin
    Frieze, Alan
    DISCRETE MATHEMATICS, 2012, 312 (21) : 3146 - 3163
  • [5] On a random graph with immigrating vertices: Emergence of the giant component
    Aldous, DJ
    Pittel, B
    RANDOM STRUCTURES & ALGORITHMS, 2000, 17 (02) : 79 - 102
  • [6] Cover Time of a Random Graph With a Degree Sequence II: Allowing Vertices of Degree Two
    Cooper, Colin
    Frieze, Alan
    Lubetzky, Eyal
    RANDOM STRUCTURES & ALGORITHMS, 2014, 45 (04) : 627 - 674
  • [7] How to determine if a random graph with a fixed degree sequence has a giant component
    Joos, Felix
    Perarnau, Guillem
    Rautenbach, Dieter
    Reed, Bruce
    2016 IEEE 57TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS), 2016, : 695 - 703
  • [8] The volume of the giant component of a random graph with given expected degrees
    Chung, Fan
    Lu, Linyuan
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 2006, 20 (02) : 395 - 411
  • [9] The evolution of the mixing rate of a simple random walk on the giant component of a random graph
    Fountoulakis, N.
    Reed, B. A.
    RANDOM STRUCTURES & ALGORITHMS, 2008, 33 (01) : 68 - 86
  • [10] Formation of a giant component in the intersection graph of a random chord diagram
    Acan, Huseyin
    Pittel, Boris
    JOURNAL OF COMBINATORIAL THEORY SERIES B, 2017, 125 : 33 - 79
12345