Consider the problem of finding a minimum weight connected subset T of edges from a weighted connected graph G. The weight of T is the sum of all the edge weights in T.
(a) Why is this problem not just the minimum spanning tree problem? Hint: think negative weight edges.
(b) Give an efficient algorithm to compute the minimum weight connected subset T.