TIME-SPACE TRADEOFFS FOR UNDIRECTED ST-CONNECTIVITY ON A GRAPH AUTOMATA

Authors
EDMONDS JA
Citation
Ja. Edmonds, TIME-SPACE TRADEOFFS FOR UNDIRECTED ST-CONNECTIVITY ON A GRAPH AUTOMATA, SIAM journal on computing (Print), 27(5), 1998, pp. 1492-1513
Citations number
25
Categorie Soggetti
Computer Science Theory & Methods",Mathematics,"Computer Science Theory & Methods",Mathematics
Journal title
SIAM journal on computing (Print) → ACNP
ISSN journal
00975397
Volume
27
Issue
5
Year of publication
1998
Pages
1492 - 1513
Database
ISI
SICI code
0097-5397(1998)27:5<1492:TTFUSO>2.0.ZU;2-O
Abstract
Undirected st-connectivity is an important problem in computing. There are algorithms for this problem that use O (n) time and ones that use O (log n) space. The main result of this paper is that, in a very nat ural structured model, these upper bounds are not simultaneously achie vable. Any probabilistic jumping automaton for graphs (JAG) requires e ither space Omega (log(2) n = log logn) or time n ((1+Omega(1 / log lo g n))) to solve undirected st-connectivity.