Short Random Walks on Graphs

DOI10.1137/S0895480194264988MaRDI QIDQ4875432zbMATH OpenFDO

Authors Greg Barnes, Uriel Feige

Publication date 24 April 1996

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

zbMATH Keywords

graphMarkov chainrandom walk

Mathematics Subject Classification ID

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

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

Cited in

(14)

• On a Result of Aleliunas et al. Concerning Random Walks on Graphs
• Random walks on quasirandom graphs
• A tight upper bound on acquaintance time of graphs
• Fast graphs for the random walker
• The electrical resistance of a graph captures its commute and cover times
• Markov incremental constructions
• A spectrum of time-space trade-offs for undirected \(s-t\) connectivity
• Undirected \(s\)--\(t\) connectivity in polynomial time and sublinear space
• On the trace of random walks on random graphs
• A fast randomized LOGSPACE algorithm for graph connectivity
• Small subgraphs in the trace of a random walk
• Speeding up random walks with neighborhood exploration
• New bounds for edge-cover by random walk
• scientific article; zbMATH DE number 38158 (Why is no real title available?)

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)