in Programming
2,862 views
3 votes
3 votes
Suppose graph G has minimum spanning tree computed.How  quickly can we update minimum spanning tree if we add new vertex and incident edges to G?
in Programming
2.9k views

2 Answers

0 votes
0 votes
Best answer

T.C is O(VlogV)  following screenshot is taken from solution manual of Coreman's book:

selected
1 vote
1 vote
Adding vertex  and incident edges to minimum.spanning tree we get a graph.Check for cycles in graph and remove max edge from each  cycle..this will give new spanning tree

1 comment

Can you please explain what is the meaning of this statement :

How  quickly can we update minimum spanning tree if we add new vertex and incident edges to G?

0
0