Undirected s--t connectivity in polynomial time and sublinear space
DOI10.1007/BF01202039zbMATH Open0872.05030MaRDI QIDQ677988FDOQ677988
Authors: Greg Barnes, Walter L. Ruzzo 
Publication date: 29 May 1997
Published in: Computational Complexity (Search for Journal in Brave)
Recommendations
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Connectivity (05C40) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Parallel algorithms in computer science (68W10)
Cites Work
- Title not available (Why is that?)
- Relationships between nondeterministic and deterministic tape complexities
- Efficiency of a Good But Not Linear Set Union Algorithm
- Multiparty protocols, pseudorandom generators for Logspace, and time- space trade-offs
- Short Random Walks on Graphs
- Symmetric space-bounded computation
- \(\text{RL}\subseteq \text{SC}\)
- Time-space tradeoffs for undirected graph traversal by graph automata
- Space Lower Bounds for Maze Threadability on Restricted Machines
- Trading Space for Time in Undirected s-t Connectivity
- Lower bounds on the length of universal traversal sequences
- Universal traversal sequences of length \(n^{0(\log \,n)}\) for cliques
- Universal traversal sequences for expander graphs
- Bounds on Universal Sequences
- Universal traversal sequences for paths and cycles
- Two Applications of Inductive Counting for Complementation Problems
- Lower Bounds on Universal Traversal Sequences for Cycles and Other Low Degree Graphs
- Time-space trade-offs for undirected st-connectivity on a JAG
- Universal sequences for complete graphs
Cited In (10)
- An O (log( n ) 4/3 ) space algorithm for ( s, t ) connectivity in undirected graphs
- Faster walks in graphs: a \(\tilde O(n^2)\) time-space trade-off for undirected \(s\)-\(t\) connectivity
- StUSPACE(log n) ⊂-DSPACE(log2 n/log log n)
- STCON in directed unique-path graphs
- Undirected ST-connectivity in log-space
- Relating sublinear space computability among graph connectivity and related problems
- Title not available (Why is that?)
- FST TCS 2003: Foundations of Software Technology and Theoretical Computer Science
- On expander graphs and connectivity in small space
- Parameterized graph connectivity and polynomial-time sub-linear-space short reductions (preliminary report)
This page was built for publication: Undirected \(s\)--\(t\) connectivity in polynomial time and sublinear space
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q677988)
