An Efficient Implementation of Edmonds' Algorithm for Maximum Weight Matching on Graphs ; CU-CS-075-75
Harold N. Gabow · CU Scholar (University of Colorado Boulder) · 1975
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.