Streaming Algorithms for Network Design

Chandra Chekuri, Rhea Jain, Sepideh Mahabadi +1

We consider the Survivable Network Design problem (SNDP) in the single-pass insertion-only streaming model. The input to SNDP is an edge-weighted graph $G=(V,E)$ and an integer…