Document Type

Technical Report

Publication Date

Summer 8-1-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.