Random Walks on Regular and Irregular Graphs

DOI10.1137/S0895480193260595zbMath0853.05075OpenAlexW2091147489MaRDI QIDQ4881294

James B. Shearer, Don Coppersmith

Publication date: 9 December 1996

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

Full work available at URL: https://doi.org/10.1137/s0895480193260595

zbMATH Keywords

random walkuniform probabilitycycle ordercycle cover time

Mathematics Subject Classification ID

Sums of independent random variables; random walks (60G50) Graph theory (including graph drawing) in computer science (68R10) Graph theory (05C99)

Related Items (12)

A fast randomized LOGSPACE algorithm for graph connectivity ⋮ Random Walks with the Minimum Degree Local Rule Have $O(n^2)$ Cover Time ⋮ A fast randomized LOGSPACE algorithm for graph connectivity ⋮ A spectrum of time-space trade-offs for undirected \(s-t\) connectivity ⋮ Lower bounds on partial sums of expected hitting times ⋮ Collecting coupons on trees, and the cover time of random walks ⋮ Achieving Geometric Convergence for Distributed Optimization Over Time-Varying Graphs ⋮ On partial sums of hitting times ⋮ Hubs-biased resistance distances on graphs and networks ⋮ New bounds for randomized busing ⋮ Chung-Yau Invariants and Graphs with Symmetric Hitting Times ⋮ Solution to a conjecture on a Nordhaus-Gaddum type result for the Kirchhoff index

This page was built for publication: Random Walks on Regular and Irregular Graphs