Hi all,
While learning about minimum spanning trees a while back, I encountered the following problem:
Given a connected undirected graph $$$G = (V, E)$$$ and a subset of vertices $$$S = {v_1, v_2, \ldots, v_n}$$$, find a forest in which each vertex $$$v \in V \setminus S$$$ is connected to exactly one vertex of $$$S$$$ such that this forest has minimum total length (sum of edge weights).
I vaguely remember that the solution to this problem involved reducing the problem to a minimum spanning tree problem. In particular, a graph $$$G'$$$ was constructed in which one could run the minimum spanning tree on $$$G'$$$ in order to retrieve the final answer. However, I've forgotten the solution, and I'm wondering if someone can explain the solution to me.
Thanks