A sublinear space, polynomial time algorithm for directed s-t connectivity

Greg Barnes, Jonathan F. Buss, Walter L. Ruzzo, Baruch Schieber

Research output: Chapter in Book/Report/Conference proceedingConference contribution

22 Scopus citations

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Θ(√log n) space while still running in polynomial time.

Original languageEnglish (US)
Title of host publicationProceedings of the Seventh Annual Structure in Complexity Theory Conference
PublisherPubl by ERROR: no PUB record found for PX none CN nonpie IG 75516
Pages27-33
Number of pages7
ISBN (Print)081862955X
StatePublished - Dec 1 1992
Externally publishedYes
EventProceedings of the Seventh Annual Structure in Complexity Theory Conference - Boston, MA, USA
Duration: Jun 22 1992Jun 25 1992

Publication series

NameProceedings of the Seventh Annual Structure in Complexity Theory Conference

Conference

ConferenceProceedings of the Seventh Annual Structure in Complexity Theory Conference
CityBoston, MA, USA
Period6/22/926/25/92

All Science Journal Classification (ASJC) codes

  • Engineering(all)

Fingerprint

Dive into the research topics of 'A sublinear space, polynomial time algorithm for directed s-t connectivity'. Together they form a unique fingerprint.

Cite this