On the Cover Time of Dense Graphs

DOI10.1137/18M122039XzbMath1420.60007arXiv1810.04772OpenAlexW2965991765MaRDI QIDQ5232158

Colin Cooper, Wesley Pegden, Alan M. Frieze

Publication date: 29 August 2019

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1810.04772

zbMATH Keywords

deterministic algorithmcover timedense graphs

Mathematics Subject Classification ID

Combinatorial probability (60C05)

Related Items

On the rank of a random binary matrix

Cites Work

• Unnamed Item
• Unnamed Item
• The cover times of random walks on random uniform hypergraphs
• Stationary distribution and cover time of random walks on random digraphs
• Cover times, blanket times, and majorizing measures
• The cover time of the preferential attachment graph
• Covering problems for Brownian motion on spheres
• Exponential concentration of cover times
• On the cover time of random walks on graphs
• A polynomial time approximation scheme for computing the supremum of Gaussian processes
• Asymptotics of cover times via Gaussian free fields: bounded-degree graphs and general trees
• Concentration inequalities for Markov chains by Marton couplings and spectral methods
• The cover time of random geometric graphs
• Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
• The cover time of sparse random graphs
• The cover time of the giant component of a random graph
• A tight upper bound on the cover time for random walks on graphs
• A tight lower bound on the cover time for random walks on graphs
• The Cover Time of Random Regular Graphs