BIB-VERSION:: CS-TR-v2.0
          ID:: STAN//CS-TR-72-328
       ENTRY:: October 16, 1995
ORGANIZATION:: Stanford University, Department of Computer Science
       TITLE:: An efficient implementation of Edmonds' maximum matching
               algorithm.
        TYPE:: Technical Report
      AUTHOR:: Gabow, Harold N.
        DATE:: June 1972
       PAGES:: 78
    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.
       NOTES:: [Adminitrivia V1/Prg/19951016]
         END:: STAN//CS-TR-72-328