STCON in directed unique-path graphs

DOI10.4230/LIPICS.FSTTCS.2008.1758MaRDI QIDQ3165964zbMATH OpenOpenAlexFDO

Authors Sampath Kannan, Sanjeev Khanna, Sudeepa Roy

Publication date 19 October 2012

Full work available at URL http://subs.emis.de/LIPIcs/frontdoor_0d80.html

zbMATH Keywords

complexitypolynomial-time algorithmst-connectivity

Mathematics Subject Classification ID

Paths and cycles (05C38) Connectivity (05C40) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms (68W40)

Recommendations

• Undirected ST-connectivity in log-space
• Undirected \(s\)--\(t\) connectivity in polynomial time and sublinear space
• Undirected connectivity in log-space
• An $O(\logn \log\logn)$ Space Algorithm for Undirected st-Connectivity
• An O (log( n ) ^4/3 ) space algorithm for ( s, t ) connectivity in undirected graphs

Cited in

(1)

• scientific article; zbMATH DE number 7754308 (Why is no real title available?)

This page was built for publication: STCON in directed unique-path graphs

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