A spectrum of time-space trade-offs for undirected \(s-t\) connectivity

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

zbMATH Keywords

random walk

Mathematics Subject Classification ID

Parallel algorithms in computer science (68W10)

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