I have a graph matching problem that I want to solve. This problem involves a weighted undirected graph and is very similar to the maximum weighted graph matching problem http://jorisvr.nl/maximummatching.html With respect to a weighted graph, a maximum weight matching is a matching for which the sum of the weights of the matched edges is as large as possible. I can find some software for solving this problem. However, my problem is a little bit different from the standard one in that I wish the number of selected edges in the matching is smaller than or equal to some predetermined constant K. I want to know how to solve this problem or if there is any approximate solution to this problem.
try greedy,pick the edges with the largest weights. A little DP seems work as well.
involves that equal problem
【在 t****a 的大作中提到】 : I have a graph matching problem that I want to solve. This problem involves : a weighted undirected graph and is very similar to the maximum weighted : graph matching problem http://jorisvr.nl/maximummatching.html : With respect to a weighted graph, a maximum weight matching is a matching : for which the sum of the weights of the matched edges is as large as : possible. I can find some software for solving this problem. : However, my problem is a little bit different from the standard one in that : I wish the number of selected edges in the matching is smaller than or equal : to some predetermined constant K. I want to know how to solve this problem : or if there is any approximate solution to this problem.