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 条

[31] The size of the giant high-order component in random hypergraphs
Cooley, Oliver
Kang, Mihyun
Koch, Christoph
RANDOM STRUCTURES & ALGORITHMS, 2018, 53 (02) : 238 - 288
[32] 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
[33] THE ASYMPTOTIC VARIANCE OF THE GIANT COMPONENT OF CONFIGURATION MODEL RANDOM GRAPHS
Ball, Frank
Neal, Peter
ANNALS OF APPLIED PROBABILITY, 2017, 27 (02) : 1057 - 1092
[34] THE COMPONENT SIZES OF A CRITICAL RANDOM GRAPH WITH GIVEN DEGREE SEQUENCE
Joseph, Adrien
ANNALS OF APPLIED PROBABILITY, 2014, 24 (06) : 2560 - 2594
[35] COVER TIME FOR BRANCHING RANDOM WALKS ON REGULAR TREES
Roberts, Matthew, I
JOURNAL OF APPLIED PROBABILITY, 2022, 59 (01) : 256 - 277
[36] Collecting coupons on trees, and the cover time of random walks
Feige, U
COMPUTATIONAL COMPLEXITY, 1997, 6 (04) : 341 - 356
[37] 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
[38] The cover times of random walks on random uniform hypergraphs
Cooper, Colin
Frieze, Alan
Radzik, Tomasz
THEORETICAL COMPUTER SCIENCE, 2013, 509 : 51 - 69
[39] On the Connectivity and Giant Component Size of Random K-out Graphs Under Randomly Deleted Nodes
Elumar, Eray Can
Sood, Mansi
Yagan, Osman
2021 IEEE INTERNATIONAL SYMPOSIUM ON INFORMATION THEORY (ISIT), 2021, : 2572 - 2577
[40] Filtering Random Graph Processes Over Random Time-Varying Graphs
Isufi, Elvin
Loukas, Andreas
Simonetto, Andrea
Leus, Geert
IEEE TRANSACTIONS ON SIGNAL PROCESSING, 2017, 65 (16) : 4406 - 4421

← 1 2 3 4 5 →