An O (log( n ) 4/3 ) space algorithm for ( s, t ) connectivity in undirected graphs

DOI10.1145/333979.333984MaRDI QIDQ5385338zbMATH OpenOpenAlexWikidataFDO

Authors Roy Armoni, Amnon Ta-Shma, A. 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

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• An $O(\logn \log\logn)$ Space Algorithm for Undirected st-Connectivity
• scientific article; zbMATH DE number 1256637
• Undirected \(s\)--\(t\) connectivity in polynomial time and sublinear space
• A Sublinear Space, Polynomial Time Algorithm for Directed s-t Connectivity
• A fast randomized LOGSPACE algorithm for graph connectivity
• A fast randomized LOGSPACE algorithm for graph connectivity
• Undirected ST-connectivity in log-space
• An \(O(|V|^2)\) algorithm for single connectedness
• Efficient algorithms for computing all low s-t edge connectivities and related problems
• Faster walks in graphs: a O(n^2) time-space trade-off for undirected s-t connectivity

Cited in

(24)

• RUSPACE\((\log n)\subseteq \text{DSPACE}(\log^2n/\log \log n)\)
• A fast randomized LOGSPACE algorithm for graph connectivity
• A space lower bound for \(st\)-connectivity on node-named JAGs
• The complexity of planarity testing
• Random walks on graphs and Monte Carlo methods
• Relating sublinear space computability among graph connectivity and related problems
• STCON in directed unique-path graphs
• s-t connectivity on digraphs with a known stationary distribution
• Undirected ST-connectivity in log-space
• Undirected connectivity in log-space
• An $O(\logn \log\logn)$ Space Algorithm for Undirected st-Connectivity
• Pseudorandom generators for combinatorial checkerboards
• A Sublinear Space, Polynomial Time Algorithm for Directed s-t Connectivity
• scientific article; zbMATH DE number 1256637 (Why is no real title available?)
• scientific article; zbMATH DE number 1559538 (Why is no real title available?)
• A fast randomized LOGSPACE algorithm for graph connectivity
• Derandomization beyond connectivity: undirected Laplacian systems in nearly logarithmic space
• The Bounded and Precise Word Problems for Presentations of Groups
• Pseudorandom pseudo-distributions with near-optimal error for read-once branching programs
• Many Random Walks Are Faster Than One
• On expander graphs and connectivity in small space
• Algorithms and Computation
• StUSPACE(log n) ⊂-DSPACE(log2 n/log log n)
• Undirected \(s\)--\(t\) connectivity in polynomial time and sublinear space

This page was built for publication: An O (log( n ) ^4/3 ) space algorithm for ( s, t ) connectivity in undirected graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5385338)