2 papers
cs.DS2020
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 -node input graph to be read sequen…
cs.DS2001
Optimal Augmentation for Bipartite Componentwise Biconnectivity in Linear Time
Tsan-sheng Hsu, Ming-Yang Kao
A graph is componentwise biconnected if every connected component either is an isolated vertex or is biconnected. We present a linear-time algorithm for the problem of adding the s…