Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > UNDIRECTED S:
Reports tagged with Undirected s:
TR04-114 | 21st November 2004
Vladimir Trifonov

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

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




ISSN 1433-8092 | Imprint