ON THE TIME-SPACE COMPLEXITY OF REACHABILITY QUERIES FOR PREPROCESSED GRAPHS

被引：1
作者：
HELLERSTEIN, L
KLEIN, P
WILBER, R
机构：
[1] HARVARD UNIV,CAMBRIDGE,MA 02138
[2] AT&T BELL LABS,MURRAY HILL,NJ 07974
来源：
INFORMATION PROCESSING LETTERS | 1990年 / 35卷 / 05期
基金：
美国国家科学基金会;
关键词：
Computational complexity; graph reachability; preprocessing; time-space trade-offs;
D O I：
10.1016/0020-0190(90)90055-3
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
How much can preprocessing help in solving graph problems? In this paper, we consider the problem of reachability in a directed bipartite graph, and propose a model for evaluating the usefulness of preprocessing in solving this problem. We give tight bounds for restricted versions of the model that suggest that preprocessing is of limited utility. © 1990.
引用
收藏
页码：261 / 267
页数：7
相关论文
共 9 条
1