Short Random Walks on Graphs

DOI10.1137/S0895480194264988zbMATH Open0843.60065MaRDI QIDQ4875432FDOQ4875432

Greg Barnes, Uriel Feige

Publication date: 24 April 1996

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

Recommendations

• On the time to traverse all edges of a graph
• On the cover time of random walks on graphs
• New bounds for edge-cover by random walk
• On a Result of Aleliunas et al. Concerning Random Walks on Graphs

zbMATH Keywords

graphMarkov chainrandom walk

Mathematics Subject Classification ID

Sums of independent random variables; random walks (60G50)

Cited In (9)

• Fast graphs for the random walker
• The electrical resistance of a graph captures its commute and cover times
• Title not available (Why is that?)
• A spectrum of time-space trade-offs for undirected \(s-t\) connectivity
• A tight upper bound on acquaintance time of graphs
• A fast randomized LOGSPACE algorithm for graph connectivity
• On a Result of Aleliunas et al. Concerning Random Walks on Graphs
• Markov incremental constructions
• Undirected \(s\)--\(t\) connectivity in polynomial time and sublinear space

This page was built for publication: Short Random Walks on Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4875432)