big data – Semi streaming algorithm for 2 vertices connectivity


Let $G=(V,E)$ be an undirected graph. given a pair of vertices $s,t in V$, how can we construct a semi-streaming algorithm which determines is $s$ and $v$ are connected? Is there any way to construct such an algorithm which scans the input stream only once?

Note that a semi-streaming algorithm is presented an arbitrary order of the edges of $G$ as a stream, and the algorithm can only access this input sequentially in the order it is given; it might process the input stream several times. The algorithm has a working memory consisting of $O(nâ‹…polylogn)$.