8.11

Linear-time update after changing a single edge weight

(a) e ∉ T and ẇ(e) > w(e): the edge was already excluded and only became heavier, so the present tree T is still an MST. Return T. Work = O(1).

(b) e ∉ T and ẇ(e) < w(e):
  1. Insert e into T; a single cycle C is created.
  2. Traverse the unique path in T between the endpoints of e (DFS/BFS) and remember the edge f of maximum weight on that path.
  3. If w(f) > ẇ(e) replace f by e; otherwise remove e again.
The path contains at most |V|−1 edges, so the whole procedure is Θ(|V|).

(c) e ∈ T and ẇ(e) < w(e): decreasing the weight of an edge already in the MST can only lower the total weight, never violate optimality. T is still an MST. Work = O(1).

(d) e ∈ T and ẇ(e) > w(e):
  1. Delete e; T splits into two components A and B (mark them with one DFS/BFS from either endpoint).
  2. Scan every edge of G; among those crossing the cut (one end in A, the other in B) select the minimum-weight edge f.
  3. Insert f to reconnect the components; the resulting tree is the new MST.
The DFS costs O(|V|) and the scan O(|E|), giving an overall linear-time update.

Back to Chapter 8