0

I trying to find an algorithm to the following question with one different : the edge are not distinct.

Give an efficient algorithm to test if T remains the minimum-cost spanning tree with the new edge added to G.

in this link- there is a solution but it is not for the different I wrote up: the edges are not nessecerliy distinct.

Updating a Minimum spanning tree when a new edge is inserted

someone has an idea?

Community
  • 1
  • 1
ABC
  • 47
  • 1
  • 11

2 Answers2

0

Well, the naive approach of just using Prim or Kruskal to find the min cost spanning tree of the new graph and then see which one has a lower total cost isn't too bad at O(|E|log|E|).

But we don't need to look at the whole graph.

Suppose your new edge connects vertices A and B. Let C be the parent of A. If B is not a descendent of A, then if A-B is lower cost than A-C, then T is no longer the MST and B should be the new parent of the subtree rooted at A.

If B is a descendant of A, then if A-B is shorter than any of the branches in T along the path from A to B, then T is no longer the MST, and the highest cost edge along that path should be removed, B is the root of the newly disconnected component, and should be added as a child of A.

I believe you may need to check these things a second time, reversing which vertices are A and B. The complexity of this is log|V| where the base of the log is the average number of children per node of T. In the case of T being a straight line, it's O(|V|), but otherwise, I think you could say it is O(log|V|).

Matthew Pope
  • 7,212
  • 1
  • 28
  • 49
  • thank you very much! I have one question.. how this different from just checking a path from A to B. I mean that in order to know if B is a descendent of A, I need to check with BFS.. and than I get the same solution with different edges.. what the info of the not different edges get me ? – ABC Jan 08 '16 at 11:18
  • To find out if one is a descendent of another, you don't need BFS. You can start at B and keep going up the tree. If you find A, then B is a descendant of A. If you get to the root without finding A, then B is not a descendant of A. If you know that B is a descendant of A, then you know that A is not a descendant of B and so you can skip checking the other way. – Matthew Pope Jan 08 '16 at 17:03
  • I believe this should work on a multigraph. In a simple graph, you don't need to worry about checking if A and B are already connected. This approach requires you to check, and if one is the other's parent in T, then you check whether the current edge or the newly inserted edge is the shortest. Does this answer your question? – Matthew Pope Jan 08 '16 at 17:08
0

First find an MST using one of the existing efficient algorithms.

Now adding an edge (v,w) creates a cycle in the MST. If the newly added edge has the maximum cost among the edges on the cycle then the MST remains as it is. If some other edge on the cycle has the maximum cost, then that's the edge to be removed to get a tree with lower cost.

So we need an efficient way to find the edge with the maximum value on the cycle. You can climb from v and w until you reach LCA(v, w) (the least common ancestor of v and w) to get the edge with the max cost. This takes linear time in the worst case.

If you are going to answer multiple such queries then pre-processing the MST is probably better. You can pre-process the MST to get a sparse table data structure in O(N lg N) time and then use this data structure to answer max queries in O(lg N) time in the worst case.

mrk
  • 3,061
  • 1
  • 29
  • 34