Remove edges to achieve maximum overall sum

Правка en2, от KaranJhaveri, 2024-08-22 09:53:37

I have an undirected graph with weights on each edge. I want to remove a set of edges such that each vertex has degree at most K, but I want to keep the maximum possible weighted sum of edges.

Example: 1-2 with weight 3

1-3 with weight 3

1-4 with weight 3

1-5 with weight 4

5-6 with weight 3

5-7 with weight 3

5-8 with weight 3

and K = 3

Output: we can remove edge between 1 and 5 and get maximum sum as 18

Question: Can it be solved in polynomial time complexity ? If yes, please help me understand the algorithm for the same.

Thanks

Теги graph, dynamic programming

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский KaranJhaveri 2024-08-22 09:53:37 14
en1 Английский KaranJhaveri 2024-08-22 09:53:01 598 Initial revision (published)