Jeremy Ting edited q2.tex  almost 10 years ago

Commit id: c74f46e1c15780edb2f448eff0c9d1518f89f5df

deletions | additions      

       

\includegraphics[width=3cm, height=4cm]{https://www.authorea.com/users/3837/articles/6902/master/file/algo.jpg}  \label{overflow}  \end{figure}  Consider each cloud to be a portion of the graph. So what you do is compare the edge that exists in the MST and is going into the cloud, with the ones that are going into a cloud but are not in the MST. If there exists an edge not in the MST which is cheaper and it wont break the degree constraint, then swap them (them being the edge in the MST and the one that isnt).