Relating sublinear space computability among graph connectivity and related problems

DOI10.1007/978-3-662-49192-8_2MaRDI QIDQ2794336zbMATH OpenOpenAlexFDO

Authors Tatsuya Imai, Osamu Watanabe

Publication date 10 March 2016

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-662-49192-8_2

Mathematics Subject Classification ID

Connectivity (05C40) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Parameterized graph connectivity and polynomial-time sub-linear-space short reductions (preliminary report)
• Undirected \(s\)--\(t\) connectivity in polynomial time and sublinear space
• scientific article; zbMATH DE number 1256637
• RUSPACE\((\log n)\subseteq \text{DSPACE}(\log^2n/\log \log n)\)
• An O (log( n ) ^4/3 ) space algorithm for ( s, t ) connectivity in undirected graphs

Cited in

(2)

• Parameterized graph connectivity and polynomial-time sub-linear-space short reductions (preliminary report)
• Physical ZKP for connected spanning subgraph: applications to bridges puzzle and other problems

This page was built for publication: Relating sublinear space computability among graph connectivity and related problems

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