Report Number: CS-TR-72-328
Institution: Stanford University, Department of Computer Science
Title: An efficient implementation of Edmonds' maximum matching
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.