| Linear Time |
|
|
|
|
| l | Bottleneck
is C(v¯, w¯) computations |
||
| l | Avoid. Find right “twin” w for each v |
||
|
|
|
|
|
| l | Compute using addpath
and minpath |
|||
| operations of dynamic trees [ST] |
||||
| l | Result:
O(m log3
n) time (messy) |
|||