Suppose we are given the minimum spanning tree T of a given graph G (with n vertices and m edges) and a new edge e = (u, v) of weight w that we will add to G. Give an efficient algorithm to find the minimum spanning tree of the graph G + e. Your algorithm should run in O(n) time to receive full credit.
(c) from Skiena manual
Start Prim or Kruskal alg from u or v until we reach a fragment of the given spanning tree path? Seems the new spanning tree won't change a lot from one new edge.
