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 (917 points) | 88 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
50,071 questions
53,206 answers
70,424 users