A matching on a graph is a set of edges, no two of which share a vertex. If each edge of the graph has a number, called its weight, a maximum weight matching has the greatest total weight possible. An algorithm with run-time 0(V^3), where V is the number of vertices, is presented. It is based on Edmonds’ algorithm, which has run-time 0(V^4). The algorithm uses efficient data structures for blossoms and for choosing edges in a search.
Gabow, Harold N., "An Efficient Implementation of Edmonds' Algorithm for Maximum Weight Matching on Graphs ; CU-CS-075-75" (1975). Computer Science Technical Reports. 73.