closed by
1,251 views
1 votes
1 votes
closed as a duplicate of: adding vertex to spanning tree

suppose that a graph G has MST already computed. How quickly can we update the MST if we add a new vertex and incident edges to it.

I know for the best case scenario when a single edge is incident from the newly added vertex. but for the worst case, when the newly added vertex has an edge incident to the every other vertex in the MST, then i'm getting confused as how should we proceed?

there are two solutions i've got online, which i'm attaching here for reference.

solution 1:

If there is only one edge, just add this edge.

If there are k(k > 1) edges, then we need to remmove k-1 edges. We can find cycles by Union-Find and remove the weightest edge in an union. This algorithm need (k-1) passes.

solution 2:

We first add all the edges to the new vertex. Then, we preform a DFS rooted at that vertex. As we go down, we keep track of the largest weight edge seen so far since each vertex above us in the DFS. We know from exercise 23.3-6 that in a directed graph, we don’t need to consider cross or forward edges. Every cycle that we detect will then be formed by a back edge. So, we just remove the edge of greatest weight seen since we were at the vertex that the back edge is going to. Then, we’ll keep going until we’ve removed one less than the degree of the vertex we added many edges. This will end up being linear time since we can reuse part of the DFS that we had already computed before detecting each cycle.

 

closed by

Related questions

0 votes
0 votes
1 answer
1
Alakhator asked Oct 11, 2018
1,126 views
What is the time complexity of Prim algorithm without using min heap?
1 votes
1 votes
1 answer
4
Abhilash Mishra asked Jul 4, 2018
674 views
Prove or disprove: If a directed graph G contains cycles, then TOPOLOGICAL SORT $(G)$ produces a vertex ordering that minimizes the number of “bad” edges that are inc...