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.

Public Answer

WIY21I The First Answerer