Time--Space Tradeoffs For Undirected st-Connectivity on a Graph Automata
- 1 October 1998
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 27 (5) , 1492-1513
- https://doi.org/10.1137/s0097539794277135
Abstract
No abstract availableKeywords
This publication has 8 references indexed in Scilit:
- A Sublinear Space, Polynomial Time Algorithm for Directed s-t ConnectivitySIAM Journal on Computing, 1998
- Time-Space Tradeoffs for Undirected Graph Traversal by Graph AutomataInformation and Computation, 1996
- Lower bounds on the length of universal traversal sequencesJournal of Computer and System Sciences, 1992
- On the cover time of random walks on graphsJournal of Theoretical Probability, 1989
- Space Lower Bounds for Maze Threadability on Restricted MachinesSIAM Journal on Computing, 1980
- Maze recognizing automata and nondeterministic tape complexityJournal of Computer and System Sciences, 1973
- Depth-First Search and Linear Graph AlgorithmsSIAM Journal on Computing, 1972
- Relationships between nondeterministic and deterministic tape complexitiesJournal of Computer and System Sciences, 1970