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.↵
↵
I think that one can just keep edges of the form $(u, v)$ where $u$ is in $S$ and $v$ isn't. From here, I think we can just run an MST algorithm on the graph $G'$, but I'm not entirely sure if this is correct.↵
↵
Thanks
↵
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.↵
↵
I think that one can just keep edges of the form $(u, v)$ where $u$ is in $S$ and $v$ isn't. From here, I think we can just run an MST algorithm on the graph $G'$, but I'm not entirely sure if this is correct.↵
↵
Thanks
