Let G = ( V , E ) be an (undirected) graph with costs ce 0 on the edges e E . As
ID: 3603033 • Letter: L
Question
Let G = (V,E) be an (undirected) graph with costs ce 0 on the edges e E. Assume you are given a minimum-cost spanning tree T in G. Now assume
that a new edge is added to G, connecting two nodes v, w V with cost c.
a) Give an efficient algorithm to test if T remains the minimum-cost spanning tree with the new edge added to G (but not to the tree T). Make your algorithm run in time O(|E |). Can you do it in O(|V |) time? Please note any assumptions you make about what data structure is used to represent the tree T and the graph G.
b) Suppose T is no longer the minimum-cost spanning tree. Give a linear-time algorithm (time O(|E |)) to update the tree T to the new minimum-cost spanning tree.
Explanation / Answer
Assume that both G and T are represented by adjacency lists. Also we maintain a data structure for each vertex for marking visited, the predecessor, and the distance from the predecessor.
a) If the new edge e = (v, w, c) were added to the tree T, it would result in a loop. The removal of the maximum cost edge in this loop would give us the minimum spanning tree for the new graph.
Given that T is the MST for G, for finding whether T remains the MST for G U {e}, we need to find whether there exists an edge e' on the path from v to w such that e' > e.
To find the path, we can do a breadth first search starting from v, storing the predecessor for each vertex. The reverse path can then be found by iterating over the predecessors from w.
ALGO1 (G, T, e)
Initialise v.visited = false for all v in T
Enqueue(Q, v)
v.visited = true
while Q is not empty
Vertex u = Dequeue(Q)
For all neighbours u' of u in T
If u'.visited = false
u'.visited = true
u'.predecessor = u
u'.predecessorcost = cost(u,u')
end if
end for
end while
v' = w
emax = (w.predecessor, w)
max = w.predecessorcost
while v' is not equal to v
if v'.predecessorcost > max
max = v'.predecessorcost
emax = (v'.predecessor, v)
end if
v' = v'.predecessor
end while
if cost(emax) > cost(e) return NOT A MINIMUM SPANNING TREE
else return IS A MINIMUM SPANNING TREE
In the above algorithm, enqueue and dequeue are O(1) operations. Using an adjacency list structure, the BFS has an order of complexity of O(|V| + |E|). But since T is a tree, |E| = |V| - 1. So the complexity of the BFS is O(|V|). The loop for finding the maximum cost edge in the path from v to w will iterate a maximum of |E| times. Again, since T is a tree, the order will be O(|V|). So the complexity of the algorithm is O(|V|).
b)
To update the tree, we use the same algorithm as above to get emax. If the cost of emax < e, the tree T is a spanning tree for G U {e}. If the cost is greater, e will be added to the spanning tree and emax will be removed. Addition of an edge takes O(1) time in an adjacency list structure. Deletion may require iteration over the edges in the adjacency list, so the order will be O(|E|). Again, since it is a tree, |E| = |V| - 1. So the order of complexity for this operation will also be O(|V|) = O(|E|). The complete algorithm is given below:
ALGO2 (G, T, e)
Initialise v.visited = false for all v in T
Enqueue(Q, v)
v.visited = true
while Q is not empty
Vertex u = Dequeue(Q)
For all neighbours u' of u in T
If u'.visited = false
u'.visited = true
u'.predecessor = u
u'.predecessorcost = cost(u,u')
end if
end for
end while
v' = w
emax = (w.predecessor, w)
max = w.predecessorcost
while v' is not equal to v
if v'.predecessorcost > max
max = v'.predecessorcost
emax = (v'.predecessor, v)
end if
v' = v'.predecessor
end while
if cost(emax) > cost(e)
return T - {emax} U {e}
else
return T
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.