We consider the maximum vertex-weighted matching problem (MVM), in which nonnegative weights are assigned to the vertices of a graph, the weight of a matching is the sum of the weights of the matched vertices, and we are required to compute a matching of maximum weight.
Revised: October 27, 2020 |
Published: April 14, 2019
Citation
Dobrian F., M. Halappanavar, A. Pothen, and A. AL-Herz. 2019.A 2/3- Approximation Algorithm for Vertex Weighted Matching in Bipartite Graphs.SIAM Journal on Scientific Computing 41, no. 1:A566-A591.PNNL-SA-142834.doi:10.1137/17M1140029