A fast randomized LOGSPACE algorithm for graph connectivity

DOI10.1016/S0304-3975(96)00118-1MaRDI QIDQ1349893zbMATH OpenFDO

Authors Uriel Feige

Publication date 27 February 1997

Published in Theoretical Computer Science (Search for Journal in Brave)

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• A fast randomized LOGSPACE algorithm for graph connectivity
• Undirected connectivity in log-space
• Trading Space for Time in Undirected s-t Connectivity
• An O (log( n ) ^4/3 ) space algorithm for ( s, t ) connectivity in undirected graphs

Cites work

• scientific article; zbMATH DE number 3934150 (Why is no real title available?)
• scientific article; zbMATH DE number 3338194 (Why is no real title available?)
• Computing with Noisy Information
• Random Walks on Regular and Irregular Graphs
• Random walks and the effective resistance of networks
• Short Random Walks on Graphs
• Two Applications of Inductive Counting for Complementation Problems
• Universal classes of hash functions

Cited in

(6)

• An O (log( n ) ^4/3 ) space algorithm for ( s, t ) connectivity in undirected graphs
• \(\text{RL}\subseteq \text{SC}\)
• Voronoi-like nondeterministic partition of a lattice by collectives of finite automata
• Undirected ST-connectivity in log-space
• scientific article; zbMATH DE number 795112 (Why is no real title available?)
• FST TCS 2003: Foundations of Software Technology and Theoretical Computer Science

This page was built for publication: A fast randomized LOGSPACE algorithm for graph connectivity

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