On expander graphs and connectivity in small space

zbMATH Open1099.05052MaRDI QIDQ5491024FDOQ5491024

Authors: Omer Reingold 

Publication date: 26 September 2006

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

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)

Cited In (3)

• Graph connectivities, network coding, and expander graphs
• Title not available (Why is that?)
• On Constructing Expanders for Any Number of Vertices

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)