On expander graphs and connectivity in small space

zbMATH Open1099.05052MaRDI QIDQ5491024FDOQ5491024

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)

Cited In (3)

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

   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 👍 👎
• Title not available (Why is that?) 👍 👎
• Undirected \(s\)--\(t\) connectivity in polynomial time and sublinear space 👍 👎

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)