Time-space lower bounds for directed ST-connectivity on graph automata models

被引：2

作者：

Barnes, G ^{[1
]}

Edmonds, JA

机构：

[1] Univ Waterloo, Dept Comp Sci, Waterloo, ON N2L 3G1, Canada

[2] Max Planck Inst Informat, Saarbrucken, Germany

[3] York Univ, Dept Comp Sci, N York, ON M3J 1P3, Canada

[4] Univ Toronto, Toronto, ON, Canada

来源：

SIAM JOURNAL ON COMPUTING | 1998年 / 27卷 / 04期

关键词：

time-space tradeoffs; lower bounds; JAG graph st-connectivity;

D O I：

10.1137/S0097539795294402

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

Directed st-connectivity is the problem of detecting whether there is a path from a distinguished vertex s to a distinguished vertex t in a directed graph. We prove time-space lower bounds of ST = Omega(n2 log n/log(n log n/S) and S-1/2 T = Omega(m(n log n)(1/2)) for directed st-connectivity on Cook and Rackoff's jumping automaton for graphs (JAG) model [SIAM J. Comput., 9(1980), pp. 636-652], where n is the number of vertices and m the number of edges in the input graph, S is the space, and T the time used by the JAG. These lower bounds are simple and elegant, they approach the known upper bound of T = O(m) when S approaches Theta(n log n), and they are the first time-space tradeoffs for JAGs with an unrestricted number of jumping pebbles.

引用

页码：1190 / 1202

页数：13

共 29 条

[1]

ACHLIOPTAS D, IN PRESS SIAM J COMP

[2]

Aleliunas R., 1979, 20th Annual Symposium of Foundations of Computer Science, P218, DOI 10.1109/SFCS.1979.34

[3]

Barnes G., 1993, Proceedings. 34th Annual Symposium on Foundations of Computer Science (Cat. No.93CH3368-8), P228, DOI 10.1109/SFCS.1993.366864

[4]

Barnes G., 1993, Proceedings of the Twenty-Fifth Annual ACM Symposium on the Theory of Computing, P728, DOI 10.1145/167088.167275

[5]

BARNES G, 1992, STRUCT COMPL TH CONF, P27, DOI 10.1109/SCT.1992.215378

[6]

BARNES G, IN PRESS SIAM J COMP

[7]

BARNES G, 910602 U WASH DEP CO

[8]

BARNES G, 1996, COMPUT COMPLEX, V1, P1

[9] Time-space tradeoffs for undirected graph traversal by graph automata [J].

Beame, P ;

Borodin, A ;

Raghavan, P ;

Ruzzo, WL ;

Tompa, M .

INFORMATION AND COMPUTATION, 1996, 130 (02) :101-129

[10]

BERMAN P, 1983, P 24 ANN S FDN COMP, P304

← 1 2 3 →