Нижняя оценка на задачу связности. Понятие полупотоковых алгоритмов. Проверка графа на связность и двудольность за один проход с СНМ. Двудольность, минимальное остовное дерево, мосты и компоненты реберной двусвязности через динамические деревья в один проход. Кратчайшие пути через \(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

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