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

被引:27
作者
Barnes, G
Buss, JF
Ruzzo, WL
Schieber, B
机构
[1] Univ Washington, Seattle, WA 98195 USA
[2] Univ Waterloo, Dept Comp Sci, Waterloo, ON N2L 3G1, Canada
[3] IBM Res Corp, Div Res, Thomas J Watson Res Ctr, Yorktown Hts, NY 10598 USA
关键词
graph connectivity; s-t connectivity; graph reachability; time-space tradeoff; JAG; NNJAG; NL;
D O I
10.1137/S0097539793283151
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
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 for directed s-t connectivity. For n-vertex graphs, our algorithm can use as little as n/2 Theta(root log n) space while still running in polynomial time.
引用
收藏
页码:1273 / 1282
页数:10
相关论文
共 15 条
[1]   Undirected S-T connectivity in polynomial time and sublinear space [J].
Barnes, G ;
Ruzzo, WL .
COMPUTATIONAL COMPLEXITY, 1996, 6 (01) :1-28
[2]  
Barnes G., 1993, Proceedings. 34th Annual Symposium on Foundations of Computer Science (Cat. No.93CH3368-8), P228, DOI 10.1109/SFCS.1993.366864
[3]  
BARNES G, 1992, STRUCT COMPL TH CONF, P27, DOI 10.1109/SCT.1992.215378
[4]  
Cook S. A., 1979, 11TH P ANN ACM S THE, P338
[5]   SPACE LOWER BOUNDS FOR MAZE THREADABILITY ON RESTRICTED MACHINES [J].
COOK, SA ;
RACKOFF, CW .
SIAM JOURNAL ON COMPUTING, 1980, 9 (03) :636-652
[6]  
Edmonds J., 1995, Proceedings of the Twenty-Seventh Annual ACM Symposium on the Theory of Computing, P147, DOI 10.1145/225058.225103
[7]   SYMMETRIC SPACE-BOUNDED COMPUTATION [J].
LEWIS, HR ;
PAPADIMITRIOU, CH .
THEORETICAL COMPUTER SCIENCE, 1982, 19 (02) :161-187
[8]  
Nisan N., 1992, Proceedings 33rd Annual Symposium on Foundations of Computer Science (Cat. No.92CH3188-0), P24, DOI 10.1109/SFCS.1992.267822
[9]  
NISAN N., 1994, COMPUT COMPLEX, V4, P1, DOI DOI 10.1007/BF01205052
[10]  
Poon C. K., 1993, Proceedings. 34th Annual Symposium on Foundations of Computer Science (Cat. No.93CH3368-8), P218, DOI 10.1109/SFCS.1993.366865