scientific article; zbMATH DE number 795112

MaRDI QIDQ4845261zbMATHFDO

Authors Anna R. Karlin, Prabhakar Raghavan

Publication date 15 January 1996

zbMATH Keywords

connectivity in undirected graphsreducing the space complexity

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Sums of independent random variables; random walks (60G50)

Recommendations

• scientific article; zbMATH DE number 878897
• Undirected \(s\)--\(t\) connectivity in polynomial time and sublinear space
• A spectrum of time-space trade-offs for undirected \(s-t\) connectivity
• A fast randomized LOGSPACE algorithm for graph connectivity
• Trading Space for Time in Undirected s-t Connectivity

Cited in

(2)

• THE NEAREST UNVISITED VERTEX WALK ON RANDOM GRAPHS
• Faster walks in graphs: a \(\tilde O(n^2)\) time-space trade-off for undirected \(s\)-\(t\) connectivity

This page was built for publication:

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