Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I want to get the subset of k nodes from a complete, weighted graph with n nodes in total. Thus, the question is whether there is an algorithm to remove (n-k) nodes from a complete weighted graph so the subset with least edge weight remains.

Thanks, Christian

share|improve this question
Not necessarily efficient? Just remove every possible subset of $n-k$ nodes and count what edge weight remains. –  Leen Droogendijk Oct 18 '13 at 14:22
Of course, that's correct. Any suggestions for a more efficient algorithm? Probably an existent one? –  Chris Oct 18 '13 at 16:11

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.