S-T connectivity on digraphs with a known stationary distribution

DOI10.1145/1978782.1978785zbMath1295.05226OpenAlexW2055100233MaRDI QIDQ3189013

Kai-Min Chung, Omer Reingold, Salil P. Vadhan

Publication date: 9 September 2014

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1978782.1978785

zbMATH Keywords

stationary distributionrandom walkgraph reachabilitylogspace computation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20) Connectivity (05C40) Random walks on graphs (05C81) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items (3)

On Probabilistic Space-Bounded Machines with Multiple Access to Random Tape ⋮ Derandomization beyond Connectivity: Undirected Laplacian Systems in Nearly Logarithmic Space ⋮ Random walks on graphs and Monte Carlo methods

This page was built for publication: S-T connectivity on digraphs with a known stationary distribution