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

  • Published on
    30-Jun-2015

  • View
    80

  • Download
    0

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- -

Transcript

<ul><li> 1. CS , 201416 </li></ul> <p> 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 </p>

Recommended

View more >