It is known, that Minimum Weight Perfect Matching can be calculated in $O(n^3)$;
Furthermore, it is possible, that the edge sets of the Minimum Weight Perfect Matching and of the Maximum Weight Perfect Matching have non-empty intersection, which implies, that in those cases the Minimum Weight Perfect Matching is different from the Perfect Matching, that is obtained by repeatedly removing the edges of the Maximum Weight Perfect Matching from the remaining set of edges, until it constitutes to a matching, which I refer to as the Minimum Weight Final Perfect Matching (=: MWFPM).
Question:
Calculating MWFPMs iteratively as described takes $O(n^4)$ steps; are there faster algorithms for their calculation?
The reason why I am interested in those kind of matchings is owed to the speculation, that they could yield better tours for heuristics that are based on matchings.
