The cover time of a regular expander is O(n log n)

DOI10.1016/0020-0190(90)90173-UzbMath0706.68059MaRDI QIDQ918708

Ronitt Rubinfeld

Publication date: 1990

Published in: Information Processing Letters (Search for Journal in Brave)

zbMATH Keywords

random walkcover time

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Complexity of computation (including implicit computational complexity) (03D15) Enumerative combinatorics (05A99)

Related Items

Memory Efficient Anonymous Graph Exploration ⋮ The electrical resistance of a graph captures its commute and cover times ⋮ Deconstructing 1-Local Expanders ⋮ Laplace eigenvalues of graphs---a survey

Cites Work

• Unnamed Item
• Expanding graphs contain all small trees
• Constructing disjoint paths on expander graphs

This page was built for publication: The cover time of a regular expander is O(n log n)