CLRS INTRODUCTION TO ALGORITHMS 3rd Edition, CHAPTER 23 QUESTION 23.2.7 [closed]

Question

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.

 

Comments

U mean if it is a complete graph, then what will be scenario

right?

But first u need to consider if all edges of graph contains distinct edge weight or not

If all edges have distinct edge weight, then only 1 MST will be possible there too

right?

---

@srestha

Ma'am, i guess what i'm trying to say is unclear.

i'm saying that, suppose M is my MST. now a vertex v is added to the MST, and there is an edge from vertex v to every other vertex in the MST M,..., then what will be the scenario. As we can see that this is not the case of complete graph. (this is because, we are adding vertex and edged to the MST not the original graph)

---

then it will be no more an mst.

because, then it will definitely form a cycle

---

Ma'am this is what the question is... How quickly can we update the MST..

---

this is ur solution I think

Don't know if your algorithm is correct, but it doesn't seem O(|V|) at least, because getting the "smallest edge not in T" of a vertex cannot be done in O(1).

The most usual way to add an edge e=(u, v) into a MST T is:

• Run a BFS in T from u to v to detect the edge with maximum value in that path. (O(|V|))
• If that edge's weight is greater than the weight of the edge you're trying to add, remove that old edge and add the new one. Otherwise, do nothing, because the new edge would not improve the MST. (O(1)).

The rationale behind this solution is that simply adding the edge into T would create exactly one cycle, and to restore the MST property you have to remove the edge with maximum value from that cycle.

if more problem, plz tell me

ref https://stackoverflow.com/questions/30881340/update-minimum-spanning-tree-if-edge-is-added 

---

yes Ma'am, problem.

in the link you have attached, the question is that a single edge is added to the graph G. but in the question i've asked, they are adding a vertex and the edges incident from it to the MST.

both the questions are different in the number of vertices and edges added.

if we are adding a single edge to the graph, solution will be simpler in the sense that we will simply add the new edge to the MST and then apply BFS or DFS for the cycle and removing heaviest edge,

but when we are adding arbitrary number of edges(we don't know how many), then the solution would be slightly complex i think. that's where i'm stuck.

---

@srestha Ma'am,

this question was already asked.. i just saw.

https://gateoverflow.in/19754/adding-vertex-to-spanning-tree

in the 1st answer, it is given that complexity will be O(VlogV). 

---

u mean fibonacci heap can do this.

how?

---

generic algo will be applied here

GENERIC-MST(G; w)
A=0;
while A does not form a spanning tree
find an edge (u,v)  that is safe for A
A = AU(u,v) 
return A

because kruskal,primes already do it by greedy algo

but in case of tie what we need to do , can done by grneric algo only

right?

---

is it visible?

---

Yes ma'am it's visible.

I'm just looking over the algorithm page you shared.

---

But I'm not getting why apply generic algorithm.

---

if there is a tie

how u evaluate it?

---

We can chose any of the edge.

---

no, I think u must have to choose safe edge one

right?