 |
 |
16 of 18 |  |
 |
 |
MIT
Results
l
Find all minimum cuts in O(n² log n) time
»
tree packing (MST computations)
»
least common ancestors
»
treefix
(array computations)
l
Improves
O(n² log³
n) of [KS]
l
Near “optimal” since can be n
2
min-cuts
l
Parallelizes
with
n
2
processors