The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
0 votes
Suppose that a graph G has a minimum spanning tree already computed. How quickly can we update the minimum spanning tree if we add a new vertex and incident edges to G?
asked in Algorithms by Junior (897 points) | 76 views
Algorithm requires (E-1) passes hence O(E) time is required.
Suppose e has  the least edge weight among the new edges formed between G and the new vertex v

Then the new mst will be the (previous computed mst +e)

This would take O(E) time.

1 Answer

+1 vote
Apply prims algorithm here.Consider newly added vertex as starting vertex.So how will you proceed farther?You must take the least weighted edge adjacent to that vertex.After doing this you are done.Because the other component was MST already and now also overall spanning tree is minimum.
answered by Active (4.2k points)

Related questions

+5 votes
2 answers

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

47,259 questions
51,483 answers
66,769 users