file.pdf (198.65 kB)

Random Walks with Look-ahead in Scale-free Random Graphs

Download (198.65 kB)
journal contribution
posted on 20.03.2010, 00:00 by Colin Cooper, Alan Frieze

If m ≥ 2 is constant and 0 ≤ r ≤ ε log log n for a small positive constant ε, then whp a random walk with look-ahead r on a scale-free graph G = G(m,n) has cover time CG(r) ∼ (2/(mr−1 (m − 1))) n log n.

History

Publisher Statement

Copyright © 2010 Society for Industrial and Applied Mathematics

Date

20/03/2010

Exports

Exports