Key points are not available for this paper at this time.
Abstract An efficient procedure for solving minimum weight perfect matching problems is presented. Starting from the empty matching the optimal matching is constructed by successively augmenting along shortest augmenting paths. Such paths can be determined via a special labeling technique. The algorithm is motivated by purely combinatorially natured optimality criteria using the concept of admissible transformations of the cost coefficients. We report on some experience with computer implementations of two different versions of this method and an implementation of Edmonds' BLOSSOM‐algorithm which makes use of Lawler's labeling technique. Though all three methods are comparable with respect to computational complexity the results indicate that the shortest augmenting path method is superior with respect to running time and that even larger problems may be solved in a reasonable amount of time.
Ulrich Derigs (Tue,) studied this question.