Efficient algorithms for maximum weight matchings in general graphs with small edge weights
Chien‐Chung Huang, Telikepalli Kavitha · 2012
Let G = (V,E) be a graph with positive integral edge weights. Our problem is to find a matching of maximum weight in G. We present a simple iterative algorithm for this problem that uses a maximum cardinality matching al-gorithm as a subroutine. Using the current fastest maximum cardinality matching algorithms, we solve the maximum weight matching problem in O(W nm logn(n 2/m)) time, or in O(Wnω) time with high probability, where n = |V |, m = |E|, W is the largest edge weight, and ω < 2.376 is the exponent of matrix multiplication. In relatively dense graphs, our algorithm performs better than all existing al-gorithms with W = o(log1.5 n). Our technique hinges on exploiting Edmonds ’ matching polytope and its dual. 1