Institution: Stanford University, Department of Computer Science

Title: An efficient implementation of Edmonds' maximum matching algorithm.

Author: Gabow, Harold N.

Date: June 1972

Abstract: A matching in a graph is a collection of edges, no two of which share a vertex. A maximum matching contains the greatest number of edges possible. This paper presents an efficient implementation of Edmonds' algorithm for finding maximum matchings. The computation time is proportional to $V^3$, where V is the number of vertices; previous algorithms have computation time proportional to $V^4$. The implementation avoids Edmonds' blossom reduction by using pointers to encode the structure of alternating paths.

http://i.stanford.edu/pub/cstr/reports/cs/tr/72/328/CS-TR-72-328.pdf