2

If there is a graph G with V vertices and E edges and I already know its minimum spanning tree T of G, and then if some of the edges from E are taken and their weights are increased by say 50, these edges may or may not be in the minimum spanning tree. Keeping the above scenario in mind is there a way to regenerate a new minimum spanning tree in linear time ? note: the number of edges whose weights have been modified are only 5.

logan
  • 21
  • 1
  • 2
  • Do you know which algorithm generated the first spanning tree? – alestanis Oct 21 '12 at 22:15
  • The first spanning tree is computed by Kruskal's algorithm. – logan Oct 21 '12 at 22:16
  • I was thinking if we can do this: 1)simply separate the edges whose weights have been adjusted from the ones whose weights have not been adjusted. 2)Then one by one insert the edges whose weights have not been modified into T to search for a cycle and eliminating the edge with hightes weight from it. But this dont seem to be linear to me. – logan Oct 21 '12 at 22:24

1 Answers1

0

You may want to take a look at the SO question here . I believe this is directly addressed in this paper by Szpira & Pan and can be done in O(n) time .

Community
  • 1
  • 1
PKG
  • 579
  • 6
  • 17
  • but can't there be a simpler solution taking into consideration that only 5 edges have been modified? – logan Oct 21 '12 at 22:42
  • 5 edges = essentially 5 times one edge @ a time, for which I gave the refs. – PKG Oct 21 '12 at 22:44