The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
0 votes
62 views
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 (887 points) | 62 views
0
Algorithm requires (E-1) passes hence O(E) time is required.
0
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.1k points)

Related questions

+5 votes
2 answers
2


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

42,455 questions
48,493 answers
154,719 comments
63,089 users