A sublinear space, polynomial time algorithm for directed s-t connectivity
- 2 January 2003
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
A deterministic sublinear space, polynomial-time algorithm for directed s-t connectivity, which is the problem of detecting whether there is a path from vertex s to vertex t in a directed graph, is presented. For n-vertex graphs, the algorithm can use as little as n/2/sup Theta /( square root log n) space while still running in polynomial time.Keywords
This publication has 6 references indexed in Scilit:
- Symmetric space-bounded computationPublished by Elsevier ,2002
- Deterministic algorithms for undirected s-t connectivity using polynomial time and sublinear space.Published by Association for Computing Machinery (ACM) ,1991
- Two Familiar Transitive Closure Algorithms Which Admit No Polynomial Time, Sublinear Space ImplementationsSIAM Journal on Computing, 1982
- Space Lower Bounds for Maze Threadability on Restricted MachinesSIAM Journal on Computing, 1980
- Deterministic CFL's are accepted simultaneously in polynomial time and log squared spacePublished by Association for Computing Machinery (ACM) ,1979
- Relationships between nondeterministic and deterministic tape complexitiesJournal of Computer and System Sciences, 1970