On the time-space complexity of reachability queries for preprocessed graphs

Lisa Hellerstein; Philip Klein; Robert Wilber

doi:10.1016/0020-0190(90)90055-3

On the time-space complexity of reachability queries for preprocessed graphs

Lisa Hellerstein, Philip Klein, Robert Wilber

Research output: Contribution to journal › Article › peer-review

Abstract

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.

Original language	English (US)
Pages (from-to)	261-267
Number of pages	7
Journal	Information Processing Letters
Volume	35
Issue number	5
DOIs	https://doi.org/10.1016/0020-0190(90)90055-3
State	Published - Aug 28 1990

Keywords

Computational complexity
graph reachability
preprocessing
time-space trade-offs

ASJC Scopus subject areas

Theoretical Computer Science
Signal Processing
Information Systems
Computer Science Applications

Access to Document

10.1016/0020-0190(90)90055-3

Cite this

@article{6709686e33a94a95bf072ba918e0a704,

title = "On the time-space complexity of reachability queries for preprocessed graphs",

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

keywords = "Computational complexity, graph reachability, preprocessing, time-space trade-offs",

author = "Lisa Hellerstein and Philip Klein and Robert Wilber",

note = "Funding Information: * Research supported by NSF Grant CCR-8411954 and by the AT&T Bell Labs GRPW program. * * Research supported by the AT&T Bell Labs URP pro-gram, and by a fellowship from the Center for Intelligent Control Systems, with additional support from Air Force Contract AFOSR-86-0078, from PYI awarded to David Shmoys, with matching support from IBM and Sun Mi-crosystems, and from ONR grant NO001488-K-0243 and DARPA Grant NOOO39-88-CO113 at Harvard University. * * * Research supported by AT&T Bell Labs.",

year = "1990",

month = aug,

day = "28",

doi = "10.1016/0020-0190(90)90055-3",

language = "English (US)",

volume = "35",

pages = "261--267",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier B.V.",

number = "5",

}

TY - JOUR

T1 - On the time-space complexity of reachability queries for preprocessed graphs

AU - Hellerstein, Lisa

AU - Klein, Philip

AU - Wilber, Robert

N1 - Funding Information: * Research supported by NSF Grant CCR-8411954 and by the AT&T Bell Labs GRPW program. * * Research supported by the AT&T Bell Labs URP pro-gram, and by a fellowship from the Center for Intelligent Control Systems, with additional support from Air Force Contract AFOSR-86-0078, from PYI awarded to David Shmoys, with matching support from IBM and Sun Mi-crosystems, and from ONR grant NO001488-K-0243 and DARPA Grant NOOO39-88-CO113 at Harvard University. * * * Research supported by AT&T Bell Labs.

PY - 1990/8/28

Y1 - 1990/8/28

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

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

KW - Computational complexity

KW - graph reachability

KW - preprocessing

KW - time-space trade-offs

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

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

U2 - 10.1016/0020-0190(90)90055-3

DO - 10.1016/0020-0190(90)90055-3

M3 - Article

AN - SCOPUS:0025476023

SN - 0020-0190

VL - 35

SP - 261

EP - 267

JO - Information Processing Letters

JF - Information Processing Letters

IS - 5

ER -

On the time-space complexity of reachability queries for preprocessed graphs

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this