Blocking Trails for $f$-factors of Multigraphs,
46 pages.
A linear time subroutine to speed up algorithms for
f-matching problems (e.g., maximum cardinality, maximum weight).
H.N. Gabow
Algorithmica 2023
A Weight-Scaling Algorithm for f-factors of Multigraphs,
76 pages. A more concrete development of the matching algorithm of
Gabow and Tarjan (1989), extended to f-factors,
modified by a new blossom structure "e-blossoms".
H.N. Gabow
Algorithmica 2023
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).