0
$\begingroup$

I found this question from CSLR that I'm trying to figure out before my final.

You are given a weighted, connected, undirected graph G = (V, E) and one of its minimum spanning trees T ⊆ E. Now consider the following two scenarios where we modify the graph and want to get an updated MST efficiently.

(a) A new edge (u, v) with weight $w_{u,v}$ (u, v ∈ V ) is added to G, resulting in a new graph G' = (V, E ∪ {(u, v)}). How do you efficiently find a minimum spanning tree T' of G'? The algorithm’s worst-case runtime must be in O(|V|).

(b) An edge (u, v) ∈ E is removed from G, resulting in a new graph G' = (V, E − (u, v)). Assume that G' is still connected. How do you efficiently find a minimum spanning tree T' of G'? The algorithm must run as fast as possible.

I know that we're supposed to find a set with the minimum edge weight. For (a), the restriction is set that the runtime should be O(|V|), which implies that we should use an algorithm that goes through the vertices. What I don't get is how to construct such an algorithm. I know, for example, that BFS/DFS run in O(V + E), and they're two of the best algorithms discounting Dijkstra's. Any advice on how to answer the question above?

$\endgroup$
  • 1
    $\begingroup$ I'll give you a couple hints. (a): If you add an edge to a tree, the resulting graph will have exactly one... (b): If you remove an edge from a tree, the resulting graph will have at most two... (and this remembers you of what theorem?) $\endgroup$ – quicksort Mar 20 '17 at 1:25
  • $\begingroup$ @quicksort (a) will be a cycle, and (b) will become two trees. So for (a) we simply find the MST from a cycle, (all the vertexes), while (b) is running two separate MST algorithms? $\endgroup$ – Andrew Raleigh Mar 21 '17 at 0:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.