Picking K nodes in a tree to minimize nearest distance sum

Правка en1, от throwaway_1234, 2017-06-18 21:22:23

I thought of this problem and I was wondering if there is any polynomial time solution?

Given a weighted tree of N nodes, pick K nodes such that sum of distances from each node to the nearest picked node is minimized.

For K = 1, the answer is the centroid of the tree. What about K > 1 ?

Теги tree, problem

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский throwaway_1234 2017-06-18 21:22:23 351 Initial revision (published)