An O (log( n ) 4/3 ) space algorithm for ( s, t ) connectivity in undirected graphs
From MaRDI portal
Publication:5385338
DOI10.1145/333979.333984zbMath1133.68341OpenAlexW1995273909WikidataQ62398495 ScholiaQ62398495MaRDI QIDQ5385338
Amnon Ta-Shma, Roy Armoni, Avi Wigderson, Shiyu Zhou
Publication date: 5 May 2008
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/333979.333984
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Related Items (6)
The complexity of planarity testing ⋮ Pseudorandom generators for combinatorial checkerboards ⋮ The Bounded and Precise Word Problems for Presentations of Groups ⋮ Pseudorandom Pseudo-distributions with Near-Optimal Error for Read-Once Branching Programs ⋮ Random walks on graphs and Monte Carlo methods ⋮ Many Random Walks Are Faster Than One
This page was built for publication: An O (log( n ) 4/3 ) space algorithm for ( s, t ) connectivity in undirected graphs
