Trading Space for Time in Undirected s-t Connectivity
From MaRDI portal
Publication:4291560
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)
68Q25: Analysis of algorithms and problem complexity
60G50: Sums of independent random variables; random walks
68R10: Graph theory (including graph drawing) in computer science
05C85: Graph algorithms (graph-theoretic aspects)
05C40: Connectivity
Related Items
Memory Efficient Anonymous Graph Exploration, 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, Tight bounds for the cover time of multiple random walks, Static and expanding grid coverage with ant robots: complexity results, Undirected \(s\)--\(t\) connectivity in polynomial time and sublinear space, A spectrum of time-space trade-offs for undirected \(s-t\) connectivity, The electrical resistance of a graph captures its commute and cover times, The cover time of deterministic random walks for general transition probabilities, The multi-agent rotor-router on the ring: a deterministic alternative to parallel random walks
