Нижняя оценка на задачу связности. Понятие полупотоковых алгоритмов. Проверка графа на связность и двудольность за один проход с СНМ. Двудольность, минимальное остовное дерево, мосты и компоненты реберной двусвязности через динамические деревья в один проход. Кратчайшие пути через $t$-спаннер с использованием $O(n^{1 + \frac{2}{t}})$ памяти. Поиск взвешенного и невзвешенного паросочетания: 5.83- и 2-приближения. Поиск числа треугольников в один проход без эскиза использованием $O(\varepsilon^{-2} (\log\frac{1}{\delta}) \frac{mn}{T})$ памяти и с эксизом при $O(\varepsilon^{-2} (\log\frac{1}{\delta}) (\frac{mn}{T})^2)$ памяти.

On Graph Problems in a Semi-Streaming Model, Feigenbaum, Kannan, McGregor, Suri, Zhang (там есть 5.83-приближение для паросочетания и многое другое)

A Data Structure for Dynamic Trees, Sleator, Tarjan, 1982

Динамические деревья на русском