Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR04-114 | 21st November 2004 00:00

An O(log n log log n) Space Algorithm for Undirected s,t-Connectivity

RSS-Feed




TR04-114
Authors: Vladimir Trifonov
Publication: 2nd December 2004 02:17
Downloads: 1913
Keywords: 


Abstract:

We present a deterministic O(log n log log n) space algorithm for
undirected s,t-connectivity. It is based on the deterministic EREW
algorithm of Chong and Lam (SODA 93) and uses the universal
exploration sequences for trees constructed by Kouck\'y (CCC 01).
Our result improves the O(log^{4/3} n) bound of Armoni et al.
(STOC 97) and is a big step towards the optimal O(log n).
Independently of our result and using a different set of techniques,
the optimal bound was achieved recently by Reingold (ECCC TR04-94).



ISSN 1433-8092 | Imprint