Document Type

Technical Report

Publication Date

Spring 3-1-1975


A matching on a graph is a set of edges, no two of which shared a vertex. A maximum matching contains the greatest number of edges possible. This paper presents an efficient implementation of Edmonds’ algorithm for finding a maximum matching. The computation time is proportional to V^3, where V is the number of vertices; previous implementation of Edmonds’ algorithm have computation time proportional to V^4. The implementation is based on a system of labels that encodes the structure of alternating paths.