Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|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.