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
↵
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
