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 条
  • [41] A time-invariant random graph with splitting events
    Georgakopoulos, Agelos
    Haslegrave, John
    ELECTRONIC COMMUNICATIONS IN PROBABILITY, 2021, 26
  • [42] Solving Vertex Cover in Polynomial Time on Hyperbolic Random Graphs
    Thomas Bläsius
    Philipp Fischbeck
    Tobias Friedrich
    Maximilian Katzmann
    Theory of Computing Systems, 2023, 67 : 28 - 51
  • [43] Limit law for the cover time of a random walk on a binary tree
    Dembo, Amir
    Rosen, Jay
    Zeitouni, Ofer
    ANNALES DE L INSTITUT HENRI POINCARE-PROBABILITES ET STATISTIQUES, 2021, 57 (02): : 830 - 855
  • [44] The cover time of deterministic random walks for general transition probabilities
    Shiraga, Takeharu
    THEORETICAL COMPUTER SCIENCE, 2020, 815 : 153 - 162
  • [45] Giant Components in Biased Graph Processes
    Amir, Gideon
    Gurel-Gurevich, Ori
    Lubetzky, Eyal
    Singer, Amit
    INDIANA UNIVERSITY MATHEMATICS JOURNAL, 2010, 59 (06) : 1893 - 1929
  • [46] Solving Vertex Cover in Polynomial Time on Hyperbolic Random Graphs
    Blaesius, Thomas
    Fischbeck, Philipp
    Friedrich, Tobias
    Katzmann, Maximilian
    THEORY OF COMPUTING SYSTEMS, 2023, 67 (01) : 28 - 51
  • [47] Solving Vertex Cover in Polynomial Time on Hyperbolic Random Graphs
    Blaesius, Thomas
    Fischbeck, Philipp
    Friedrich, Tobias
    Katzmann, Maximilian
    37TH INTERNATIONAL SYMPOSIUM ON THEORETICAL ASPECTS OF COMPUTER SCIENCE (STACS 2020), 2020, 154
  • [48] Existence and Size of the Giant Component in Inhomogeneous Random K-Out Graphs
    Sood, Mansi
    Yagan, Osman
    IEEE TRANSACTIONS ON INFORMATION THEORY, 2023, 69 (12) : 8081 - 8096
  • [49] A New Approach to the Giant Component Problem
    Janson, Svante
    Luczak, Malwina J.
    RANDOM STRUCTURES & ALGORITHMS, 2009, 34 (02) : 197 - 216
  • [50] An old approach to the giant component problem
    Bollobas, Bela
    Riordan, Oliver
    JOURNAL OF COMBINATORIAL THEORY SERIES B, 2015, 113 : 236 - 260
12345