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 条
  • [1] The cover time of random regular graphs
    Cooper, C
    Frieze, A
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 2005, 18 (04) : 728 - 740
  • [2] The Cover Time of Random Geometric Graphs
    Cooper, Colin
    Frieze, Alan
    RANDOM STRUCTURES & ALGORITHMS, 2011, 38 (03) : 324 - 349
  • [3] On the cover time and mixing time of random geometric graphs
    Avin, Chen
    Ercal, Gunes
    THEORETICAL COMPUTER SCIENCE, 2007, 380 (1-2) : 2 - 22
  • [4] Cover time and mixing time of random walks on dynamic graphs
    Avin, Chen
    Koucky, Michal
    Lotker, Zvi
    RANDOM STRUCTURES & ALGORITHMS, 2018, 52 (04) : 576 - 596
  • [5] Expander properties and the cover time of random intersection graphs
    Nikoletseas, S.
    Raptopoulos, C.
    Spirakis, P. G.
    THEORETICAL COMPUTER SCIENCE, 2009, 410 (50) : 5261 - 5272
  • [6] Analysis of an iterated local search algorithm for vertex cover in sparse random graphs
    Witt, Carsten
    THEORETICAL COMPUTER SCIENCE, 2012, 425 : 117 - 125
  • [7] 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
  • [8] 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
  • [9] 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
  • [10] Cover and hitting times of hyperbolic random graphs
    Kiwi, Marcos
    Schepers, Markus
    Sylvester, John
    RANDOM STRUCTURES & ALGORITHMS, 2024, 65 (04) : 915 - 978
12345