A Sublinear Space, Polynomial Time Algorithm for Directed s-t Connectivity

DOI10.1137/S0097539793283151MaRDI QIDQ4210095zbMATH OpenOpenAlexFDO

Authors Greg Barnes, Jonathan F. Buss, Walter L. Ruzzo, Baruch Schieber

Publication date 20 September 1998

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/s0097539793283151

zbMATH Keywords

reachabilityconnectivitypathpolynomial time algorithmtime-space tradeoff

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Connectivity (05C40) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Parallel algorithms in computer science (68W10)

Recommendations

• Undirected \(s\)--\(t\) connectivity in polynomial time and sublinear space
• An O (log( n ) ^4/3 ) space algorithm for ( s, t ) connectivity in undirected graphs
• \(\widetilde{O}(\sqrt{n})\)-space and polynomial-time algorithm for planar directed graph reachability
• An $O(\logn \log\logn)$ Space Algorithm for Undirected st-Connectivity
• scientific article; zbMATH DE number 1256637

Cited in

(24)

• \(\tilde{O}(n^{1/3})\)-space algorithm for the grid graph reachability problem
• A framework for in-place graph algorithms
• A polynomial time algorithm for deciding convergent transfer subgraphs in acyclic labeled directed graphs
• Space-efficient algorithms for maximum cardinality search, its applications, and variants of BFS
• Sublinear-space approximation algorithms for Max \(r\)-SAT
• Parameterized graph connectivity and polynomial-time sub-linear-space short reductions (preliminary report)
• Improved space efficient algorithms for BFS, DFS and applications
• Derandomizing isolation in space-bounded settings
• Space efficient linear time algorithms for BFS, DFS and applications
• Space-efficient algorithms for reachability in directed geometric graphs
• The 2CNF Boolean formula satisfiability problem and the linear space hypothesis
• \(\widetilde{O}(\sqrt{n})\)-space and polynomial-time algorithm for planar directed graph reachability
• Depth-First Search Using $$O(n)$$ Bits
• The complexity of graph connectivity
• Biconnectivity, \(st\)-numbering and other applications of DFS using \(O(n)\) bits
• An O (log( n ) ^4/3 ) space algorithm for ( s, t ) connectivity in undirected graphs
• A space lower bound for \(st\)-connectivity on node-named JAGs
• Space complexity of the directed reachability problem over surface-embedded graphs
• Optimal In-place Algorithms for Basic Graph Problems
• Space efficient algorithm for solving reachability using tree decomposition and separators
• Homomorphisms to oriented paths
• Frameworks for designing in-place graph algorithms
• Undirected ST-connectivity in log-space
• Directed st-Connectivity Is Not Expressible in Symmetric Datalog

This page was built for publication: A Sublinear Space, Polynomial Time Algorithm for Directed s-t Connectivity

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