Anzeige
Erschienen in:
2005 | OriginalPaper | Buchkapitel
Simulating Undirected st-Connectivity Algorithms on Uniform JAGs and NNJAGs
verfasst von : Pinyan Lu, Jialin Zhang, Chung Keung Poon, Jin-Yi Cai
Erschienen in: Algorithms and Computation
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
In a breakthrough result, Reingold [17] showed that the Undirected
st
-Connectivity problem can be solved in
O
(log
n
) space. The next major challenge in this direction is whether one can extend it to directed graphs, and thereby lowering the deterministic space complexity of
$\mathcal{RL}$
or
$\mathcal{NL}$
. In this paper, we show that Reingold’s algorithm, the
O
(log
4/3
n
)-space algorithm by Armoni et al.[3] and the
O
(log
3/2
n
)-space algorithm by Nisan et al.[14] can all be carried out on the RAM-NNJAG model [15](a uniform version of the NNJAG model [16]). As there is a tight Ω(log
2
n
) space lower bound for the Directed
st
-Connectivity problem on the RAM-NNJAG model implied by [8], our result gives an obstruction to generalizing Reingold’s algorithm to the directed case.