Undirected \(s\)--\(t\) connectivity in polynomial time and sublinear space
From MaRDI portal
Publication:677988
DOI10.1007/BF01202039zbMath0872.05030MaRDI QIDQ677988
Publication date: 29 May 1997
Published in: Computational Complexity (Search for Journal in Brave)
Analysis of algorithms and problem complexity (68Q25) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Parallel algorithms in computer science (68W10) Graph algorithms (graph-theoretic aspects) (05C85) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Connectivity (05C40)
Cites Work
- Unnamed Item
- Time-space tradeoffs for undirected graph traversal by graph automata
- Universal sequences for complete graphs
- Universal traversal sequences of length \(n^{0(\log \,n)}\) for cliques
- Symmetric space-bounded computation
- Lower bounds on the length of universal traversal sequences
- Multiparty protocols, pseudorandom generators for Logspace, and time- space trade-offs
- \(\text{RL}\subseteq \text{SC}\)
- Universal traversal sequences for expander graphs
- Relationships between nondeterministic and deterministic tape complexities
- Bounds on Universal Sequences
- Universal traversal sequences for paths and cycles
- Two Applications of Inductive Counting for Complementation Problems
- Space Lower Bounds for Maze Threadability on Restricted Machines
- Lower Bounds on Universal Traversal Sequences for Cycles and Other Low Degree Graphs
- Efficiency of a Good But Not Linear Set Union Algorithm
- Trading Space for Time in Undirected s-t Connectivity
- Short Random Walks on Graphs
- Time-space trade-offs for undirected st-connectivity on a JAG
This page was built for publication: Undirected \(s\)--\(t\) connectivity in polynomial time and sublinear space
