Trading Space for Time in Undirected s-t Connectivity

DOI10.1137/S0097539790190144zbMath0804.68105MaRDI QIDQ4291560

Anna R. Karlin, Prabhakar Raghavan, Andrei Z. Broder, Eli Upfal

Publication date: 16 June 1994

Published in: SIAM Journal on Computing (Search for Journal in Brave)

zbMATH Keywords

reachabilityparallel random walksspace-time tradeoffconnectivity testing

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Sums of independent random variables; random walks (60G50) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Connectivity (05C40)

Related Items (11)

Memory Efficient Anonymous Graph Exploration ⋮ A spectrum of time-space trade-offs for undirected \(s-t\) connectivity ⋮ The multi-agent rotor-router on the ring: a deterministic alternative to parallel random walks ⋮ The electrical resistance of a graph captures its commute and cover times ⋮ Reversible random walks on dynamic graphs ⋮ Multiple random walks on graphs: mixing few to cover many ⋮ On a cover time problem on a dynamic graph with steps at random times ⋮ Static and expanding grid coverage with ant robots: complexity results ⋮ Undirected \(s\)--\(t\) connectivity in polynomial time and sublinear space ⋮ Tight bounds for the cover time of multiple random walks ⋮ The cover time of deterministic random walks for general transition probabilities

This page was built for publication: Trading Space for Time in Undirected s-t Connectivity