MIT
62
l
Bottleneck is
C
(
v
¯
,
w
¯
)
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
3
n
)
time (messy)
