The first part of this article presents a data structure for weighted
matching in time
O(n(m+n log n)).
Then we extend this to arbitrary
degree constraints. (This entails
first defining
blossoms, and then giving simple algorithms
for maximum weight b-matchings and f-factors.)
The weighted matching approach to maximum cardinality matching,
18 pages.
A complete algorithm for nonbipartite matching
in time O(
√nm).
Appendix shows the approach can give a simple
correctness proof
for the
Micali-Vazirani matching algorithm.
Also includes a detailed correctness proof of the DFS alternative
to the MV DDFS algorithm.
reference:
Fundamenta Informaticae (Elegant Structures in Computation:
To Andrzej Ehrenfeucht on His 85th Birthday)
154, 1-4, 2017, pp. 109-130.
This article presents a data structure used in the above TALG weighted
matching algorithm.
It also simplifies the implementation of the
static/incremental-tree set merging data structure of Gabow and Tarjan (1985).