typedeftemplate's blog

By typedeftemplate, history, 4 weeks ago, In English

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

 
 
 
 
  • Vote: I like it
  • +2
  • Vote: I do not like it

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by typedeftemplate (previous revision, new revision, compare).

»
4 weeks ago, # |
  Vote: I like it +13 Vote: I do not like it

Before running Kruskal's algorithm, join vertices $$$v_1,\ldots,v_n$$$ in the union-find data structure.

»
4 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Imagine there is an invisible node $$$P$$$ connected with $$$v_1,v_2,...,v_n$$$ already, then you can do any sort of MST algo.

If you use Kruskal, you just have to merge $$$v_1,v_2,...,v_n$$$ in the union data structure as they are already connected together with $$$P$$$.

If you use Prim, you should put $$$v_1,v_2,...,v_n$$$ in the queue and set them as connected to the main part of the tree.

»
12 days ago, # |
  Vote: I like it -6 Vote: I do not like it

wow!What a technique to find solution of codechef long challenge question.....Bro u just modified the question excellently in the way u wanted....

»
12 days ago, # |
  Vote: I like it -6 Vote: I do not like it

Getting the vibe of D-Dimensional MST of long challenge ;)