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

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

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 proceeding › Conference contribution

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 language	English (US)
Title of host publication	Proceedings of the Seventh Annual Structure in Complexity Theory Conference
Publisher	Publ by ERROR: no PUB record found for PX none CN nonpie IG 75516
Pages	27-33
Number of pages	7
ISBN (Print)	081862955X
State	Published - 1992
Externally published	Yes
Event	Proceedings of the Seventh Annual Structure in Complexity Theory Conference - Boston, MA, USA Duration: Jun 22 1992 → Jun 25 1992

Publication series

Name	Proceedings of the Seventh Annual Structure in Complexity Theory Conference

Conference

Conference	Proceedings of the Seventh Annual Structure in Complexity Theory Conference
City	Boston, MA, USA
Period	6/22/92 → 6/25/92

All Science Journal Classification (ASJC) codes

General Engineering

Cite this

Barnes, G., Buss, J. F., Ruzzo, W. L., & Schieber, B. (1992). A sublinear space, polynomial time algorithm for directed s-t connectivity. In Proceedings of the Seventh Annual Structure in Complexity Theory Conference (pp. 27-33). (Proceedings of the Seventh Annual Structure in Complexity Theory Conference). Publ by ERROR: no PUB record found for PX none CN nonpie IG 75516.

Barnes, Greg ; Buss, Jonathan F. ; Ruzzo, Walter L. et al. / A sublinear space, polynomial time algorithm for directed s-t connectivity. Proceedings of the Seventh Annual Structure in Complexity Theory Conference. Publ by ERROR: no PUB record found for PX none CN nonpie IG 75516, 1992. pp. 27-33 (Proceedings of the Seventh Annual Structure in Complexity Theory Conference).

@inproceedings{5e5b6538442b4d328c05cb44772c18ad,

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

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.",

author = "Greg Barnes and Buss, {Jonathan F.} and Ruzzo, {Walter L.} and Baruch Schieber",

year = "1992",

language = "English (US)",

isbn = "081862955X",

series = "Proceedings of the Seventh Annual Structure in Complexity Theory Conference",

publisher = "Publ by ERROR: no PUB record found for PX none CN nonpie IG 75516",

pages = "27--33",

booktitle = "Proceedings of the Seventh Annual Structure in Complexity Theory Conference",

note = "Proceedings of the Seventh Annual Structure in Complexity Theory Conference ; Conference date: 22-06-1992 Through 25-06-1992",

}

Barnes, G, Buss, JF, Ruzzo, WL & Schieber, B 1992, A sublinear space, polynomial time algorithm for directed s-t connectivity. in Proceedings of the Seventh Annual Structure in Complexity Theory Conference. Proceedings of the Seventh Annual Structure in Complexity Theory Conference, Publ by ERROR: no PUB record found for PX none CN nonpie IG 75516, pp. 27-33, Proceedings of the Seventh Annual Structure in Complexity Theory Conference, Boston, MA, USA, 6/22/92.

A sublinear space, polynomial time algorithm for directed s-t connectivity. / Barnes, Greg; Buss, Jonathan F.; Ruzzo, Walter L. et al.
Proceedings of the Seventh Annual Structure in Complexity Theory Conference. Publ by ERROR: no PUB record found for PX none CN nonpie IG 75516, 1992. p. 27-33 (Proceedings of the Seventh Annual Structure in Complexity Theory Conference).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

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

AU - Barnes, Greg

AU - Buss, Jonathan F.

AU - Ruzzo, Walter L.

AU - Schieber, Baruch

PY - 1992

Y1 - 1992

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0027038959&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0027038959&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:0027038959

SN - 081862955X

T3 - Proceedings of the Seventh Annual Structure in Complexity Theory Conference

SP - 27

EP - 33

BT - Proceedings of the Seventh Annual Structure in Complexity Theory Conference

PB - Publ by ERROR: no PUB record found for PX none CN nonpie IG 75516

T2 - Proceedings of the Seventh Annual Structure in Complexity Theory Conference

Y2 - 22 June 1992 through 25 June 1992

ER -

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

Abstract

Publication series

Conference

All Science Journal Classification (ASJC) codes

Other files and links

Fingerprint

Cite this