March 1, 2000Journal of the ACMOpen Access

An O (log( n ) 4/3 ) space algorithm for ( s, t ) connectivity in undirected graphs

View Full Paper

Ask AI

Bookmark

Abstract

We present a deterministic algorithm that computes st -connectivity in undirected graphs using O (log 4/3 n ) space. This improves the previous O (log 3/2 n ) bound of Nisan et al. [1992].

Discussion

No takes yet. Share an insight, caveat, or question.

Cite This Study

Armoni et al. (2000) studied this question.

synapsesocial.com/papers/6a715f7bc2d7c30908270c22 https://doi.org/10.1145/333979.333984

View Full Paper

Ask AI

Bookmark

Abstract

We present a deterministic algorithm that computes st -connectivity in undirected graphs using O (log 4/3 n ) space. This improves the previous O (log 3/2 n ) bound of Nisan et al. [1992].