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? Pooja Palod asked Oct 15, 2015 Pooja Palod 3.6k views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
Best answer 0 votes 0 votes T.C is O(VlogV) following screenshot is taken from solution manual of Coreman's book: Manu Thakur answered Aug 25, 2017 • selected Aug 25, 2017 Manu Thakur comment Share Follow See all 0 reply Please log in or register to add a comment.
1 votes 1 votes 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 Pooja Palod answered Oct 15, 2015 Pooja Palod comment Share Follow See 1 comment See all 1 1 comment reply radha gogia commented Oct 17, 2015 reply Follow Share 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 votes 0 votes Please log in or register to add a comment.