E-viri
PDF
Recenzirano
Odprti dostop
-
Gabow, Harold N
Journal of the ACM, 04/1976, Letnik: 23, Številka: 2Journal Article
A matching on a graph is a set 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 a maximum matching. The computation time is proportional to V 3 , where V is the number of vertices; previous implementations 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.
