Спарсификаторы. Построение в полупотоковом режиме за $\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