The Evolution of the Cover Time

DOI10.1017/S0963548310000489zbMath1226.05230arXiv1001.0609MaRDI QIDQ2998848

Martin T. Barlow, Yuval Peres, Asaf Nachmias, Jian Ding

Publication date: 11 May 2011

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Random walks on graphs (05C81)

Related Items

Analytical results for the distribution of cover times of random walks on random regular graphs, Sandwich theorem of cover times, On the Cover Time of the Emerging Giant, Convergence of blanket times for sequences of random walks on critical random graphs, Cover times, blanket times, and majorizing measures, A spectral characterization for concentration of the cover time, Cover Times and Generic Chaining, Cover times for sequences of reversible Markov chains on random graphs, Cover time of a random graph with a degree sequence II: Allowing vertices of degree two

Cites Work

• Unnamed Item
• Unnamed Item
• Covering problems for Markov chains
• Random walks and the effective resistance of networks
• Random walk covering of some special trees
• Random graph asymptotics on high-dimensional tori
• Critical random graphs: Diameter and mixing time
• Edge percolation on a random regular graph of low degree
• The Alexander-Orbach conjecture holds in high dimensions
• The electrical resistance of a graph captures its commute and cover times
• An introduction to covering problems for random walks on graphs
• The sizes of compact subsets of Hilbert space and continuity of Gaussian processes
• Mean-field conditions for percolation on finite graphs
• Multiple cover time
• The cover time of the giant component of a random graph
• Universal traversal sequences for paths and cycles
• Component behavior near the critical point of the random graph process
• A tight upper bound on the cover time for random walks on graphs
• The Generic Chaining
• Building uniformly random subtrees
• A tight lower bound on the cover time for random walks on graphs
• Diameters in Supercritical Random Graphs Via First Passage Percolation
• [https://portal.mardi4nfdi.de/wiki/Publication:5186512 Continuity of local times for L�vy processes]
• Random subgraphs of finite graphs: I. The scaling window under the triangle condition