Алгоритмы обработки потоковых данных, осень 2014: Лекция 7. Полупотоковые алгоритмы на графах. Базовые алгоритмы

Embed Size (px)

DESCRIPTION

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

Text of Алгоритмы обработки потоковых данных, осень 2014: Лекция...

  • 1. CS , 201416

2. n = h(u1; v1);; (ut ; vt )i. , s t.I (n). .I O(n(log n)O(1)).I Union-Find . . 3. 1 , . 2 , , . . . , . . 4. I .I Union-Find + .I . 5. link-cut n . O(log n).I add(v) .I link(u, v) .I cut(u, v) .I revert(u) u .I aggregatef (u, v) u v.I .I .I . 6. . , . . . H G t-, dG (u; v)dH(u; v)tdG (u; v).I process(u, v): dH(u; v)t, (u; v).I dist(u, v): dH(u; v).I H t-. ? 7. I H m n .I H t.I d = 2mn .I d2 .I . d2n = m .I