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