Спарсификаторы. Построение в полупотоковом режиме за \(\tilde{O}(\varepsilon^{-2} n)\). Набросок построения в режиме offline. Эскиз графа через матрицу инциндентности. \(l_0\)-сэмплирование. Поиск компонент связности через эскизы, k-связность и поиск минимального разреза.


Спарсификаторы offline за \(\tilde{O}(\varepsilon^{-2}n)\), Nicholas Harvey + ссылка на курс CPSC 536N

Data Streams & Communication Complexity, McGregor, Amherst (про эскизы графов, разрезы и k-связность)

On Unifying the Space of \(l_0\)-Sampling Algorithms, Cormode, Firmani