# Item

ITEM ACTIONSEXPORT

Released

Report

#### Time-space lower bounds for directed s-t connectivity on JAG models

##### MPS-Authors

##### Locator

There are no locators available

##### Fulltext (public)

MPI-I-94-119.pdf

(Any fulltext), 11MB

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Barnes, G., & Edmonds, J. A.(1994). *Time-space lower bounds
for directed s-t connectivity on JAG models* (MPI-I-94-119). Saarbrücken: Max-Planck-Institut für Informatik.

Cite as: http://hdl.handle.net/11858/00-001M-0000-0014-B78C-3

##### Abstract

Directed $s$-$t$ 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(n^{2}/\log n)$
and $S^{1/2}T = \Omega(m n^{1/2})$
for Cook and Rackoff's JAG model, where $n$ is the number of
vertices and $m$ the number of edges in the input graph, and
$S$ is the space and $T$ the time used by the JAG.
We also prove a time-space lower bound of
$S^{1/3}T = \Omega(m^{2/3}n^{2/3})$
on the more powerful
node-named JAG model of Poon.
These bounds approach the known upper bound
of $T = O(m)$
when $S = \Theta(n \log n)$.