A spectrum of time-space trade-offs for undirected \(s-t\) connectivity
From MaRDI portal
Publication:1356886
DOI10.1006/JCSS.1997.1471zbMath0878.68068OpenAlexW2000570573MaRDI QIDQ1356886
No author found.
Publication date: 4 January 1998
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1006/jcss.1997.1471
Related Items (4)
Bounds on the cover time of parallel rotor walks ⋮ The multi-agent rotor-router on the ring: a deterministic alternative to parallel random walks ⋮ Multiple random walks on graphs: mixing few to cover many ⋮ Many Random Walks Are Faster Than One
Cites Work
- Unnamed Item
- Time-space tradeoffs for undirected graph traversal by graph automata
- Random walks and the effective resistance of networks
- The electrical resistance of a graph captures its commute and cover times
- On the cover time of random walks on graphs
- Two Applications of Inductive Counting for Complementation Problems
- Trading Space for Time in Undirected s-t Connectivity
- A fast randomized LOGSPACE algorithm for graph connectivity
- Short Random Walks on Graphs
- Random Walks on Regular and Irregular Graphs
- Time-space trade-offs for undirected st-connectivity on a JAG
This page was built for publication: A spectrum of time-space trade-offs for undirected \(s-t\) connectivity
