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

DOI10.1137/S0097539793283151zbMath0908.05080OpenAlexW2149392423MaRDI QIDQ4210095

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

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

reachabilitypolynomial time algorithmconnectivitypathtime-space tradeoff

Mathematics Subject Classification ID

Related Items (18)

Optimal In-place Algorithms for Basic Graph Problems ⋮ Biconnectivity, \(st\)-numbering and other applications of DFS using \(O(n)\) bits ⋮ Depth-First Search Using $$O(n)$$ Bits ⋮ The complexity of graph connectivity ⋮ Space-efficient algorithms for reachability in directed geometric graphs ⋮ Space-efficient algorithms for maximum cardinality search, its applications, and variants of BFS ⋮ The 2CNF Boolean formula satisfiability problem and the linear space hypothesis ⋮ Space efficient algorithm for solving reachability using tree decomposition and separators ⋮ 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 ⋮ Frameworks for designing in-place graph algorithms ⋮ A Framework for In-place Graph Algorithms ⋮ Unnamed Item ⋮ Improved Space Efficient Algorithms for BFS, DFS and Applications ⋮ Space Complexity of the Directed Reachability Problem over Surface-Embedded Graphs ⋮ Derandomizing Isolation in Space-Bounded Settings ⋮ A space lower bound for \(st\)-connectivity on node-named JAGs ⋮ Space efficient linear time algorithms for BFS, DFS and applications

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