On expander graphs and connectivity in small space

zbMATH Open1099.05052MaRDI QIDQ5491024FDOQ5491024

Authors Omer Reingold

Publication date 26 September 2006

zbMATH Keywords

Graph connectivity, expander graphs, randomness in computation, symmetric log-space (SL), pseudorandomness

Mathematics Subject Classification ID

Connectivity (05C40) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• Undirected connectivity in log-space
• Undirected ST-connectivity in log-space
• An O (log( n ) ^4/3 ) space algorithm for ( s, t ) connectivity in undirected graphs
• scientific article; zbMATH DE number 1256637
• Undirected \(s\)--\(t\) connectivity in polynomial time and sublinear space

Cited in

(3)

• scientific article; zbMATH DE number 7378741 (Why is no real title available?)
• On Constructing Expanders for Any Number of Vertices
• Graph connectivities, network coding, and expander graphs

This page was built for publication: On expander graphs and connectivity in small space

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