Streaming Algorithms for Connectivity Augmentation

Ce Jin, Michael Kapralov, Sepideh Mahabadi +1

We study the $k$-connectivity augmentation problem ($k$-CAP) in the single-pass streaming model. Given a $(k-1)$-edge connected graph $G=(V,E)$ that is stored in memory, and a stre…