A SUBLINEAR SPACE, POLYNOMIAL-TIME ALGORITHM FOR DIRECTED S-T CONNECTIVITY

Authors
BARNES G BUSS JF RUZZO WL SCHIEBER B
Citation
G. Barnes et al., A SUBLINEAR SPACE, POLYNOMIAL-TIME ALGORITHM FOR DIRECTED S-T CONNECTIVITY, SIAM journal on computing, 27(5), 1998, pp. 1273-1282
Citations number
15
Categorie Soggetti
Computer Science Theory & Methods",Mathematics,"Computer Science Theory & Methods",Mathematics
Journal title
SIAM journal on computing → ACNP
ISSN journal
00975397
Volume
27
Issue
5
Year of publication
1998
Pages
1273 - 1282
Database
ISI
SICI code
0097-5397(1998)27:5<1273:ASSPAF>2.0.ZU;2-Q
Abstract
Directed s-t connectivity is the problem of detecting whether there is a path from vertex s to vertex t in a directed graph. We present the first known deterministic sublinear space, polynomial time algorithm f or directed s-t connectivity. For n-vertex graphs, our algorithm can u se as little as n/2 Theta(root log n) space while still running in pol ynomial time.