Streaming Complexity of Spanning Tree Computation

Yi-Jun Chang, Martin Farach-Colton, Tsan-Sheng Hsu +1

The semi-streaming model is a variant of the streaming model frequently used for the computation of graph problems. It allows the edges of an $n$-node input graph to be read sequen…