 |
 |
17 of 18 |  |
 |
 |
MIT
l
Bottleneck is
computations
l
Avoid. Find right “twin” w
for each v
Linear Time
l
Compute using
addpath
and
minpath
operations of dynamic trees
[ST]
l
Result: O
(m log³
n)
time
(
)
C
v
w
¯
¯
,
(
)
(
)
(
)
(
)
C
v
C
w
C
v
w
w
¯
¯
¯
¯
+
-
min
,
2