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

共 10 条

[1]

ALELIUNAS R, 1979, P 20 ANN S FDN COMP, P218, DOI DOI 10.1109/SFCS.1979.34

[2] AN ALGORITHM FOR FINDING HAMILTON PATHS AND CYCLES IN RANDOM GRAPHS [J].

BOLLOBAS, B ;

FENNER, TI ;

FRIEZE, AM .

COMBINATORICA, 1987, 7 (04) :327-341

[3]

Bollobas B., 2001, CAMBRIDGE STUDIES AD, V73

[4]

BRODER A, 1989, J THEORET PROBAB, V2, P101

[5] A TIGHT LOWER-BOUND ON THE COVER TIME FOR RANDOM-WALKS ON GRAPHS [J].

FEIGE, U .

RANDOM STRUCTURES & ALGORITHMS, 1995, 6 (04) :433-438

[6] A TIGHT UPPER BOUND ON THE COVER TIME FOR RANDOM-WALKS ON GRAPHS [J].

FEIGE, U .

RANDOM STRUCTURES & ALGORITHMS, 1995, 6 (01) :51-54

[7]

Janson S, 2000, WIL INT S D, DOI 10.1002/9781118032718

[8]

Jerrum M., 1996, Approximation Algorithms for NP-Hard Problems, chapter The Markov Chain Monte Carlo Method: An Approach To Approximate Counting And Integration, P482

[9] On the cover time for random walks on random graphs [J].

Jonasson, J .

COMBINATORICS PROBABILITY & COMPUTING, 1998, 7 (03) :265-279

[10]

os P., 1959, Publ. Math, V6, P290, DOI DOI 10.5486/PMD.1959.6.3-4.12

← 1 →