Undirecteds-t connectivity in polynomial time and sublinear space
- 1 March 1996
- journal article
- research article
- Published by Springer Nature in computational complexity
- Vol. 6 (1) , 1-28
- https://doi.org/10.1007/bf01202039
Abstract
No abstract availableKeywords
This publication has 26 references indexed in Scilit:
- A sublinear space, polynomial time algorithm for directed s-t connectivityPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Short Random Walks on GraphsSIAM Journal on Discrete Mathematics, 1996
- Multiparty protocols, pseudorandom generators for logspace, and time-space trade-offsJournal of Computer and System Sciences, 1992
- Deterministic algorithms for undirected s-t connectivity using polynomial time and sublinear space.Published by Association for Computing Machinery (ACM) ,1991
- Universal sequences for complete graphsDiscrete Applied Mathematics, 1990
- Two Applications of Inductive Counting for Complementation ProblemsSIAM Journal on Computing, 1989
- Bounds on Universal SequencesSIAM Journal on Computing, 1989
- Random walks, universal traversal sequences, and the complexity of maze problemsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1979
- Efficiency of a Good But Not Linear Set Union AlgorithmJournal of the ACM, 1975
- Relationships between nondeterministic and deterministic tape complexitiesJournal of Computer and System Sciences, 1970