A Simplification of the MV Matching Algorithm and its Proof

On combinatorial properties of matrices

J. Egerváry · 1931

Earlier work this paper cites.

Graphs and matrices

D. Konig · 1931

Earlier work this paper cites.

The Hungarian method for the assignment problem

H.W. Kuhn · 1955

Earlier work this paper cites.

College admissions and the stability of marriage

D. Gale and L. S. Shapley · 1962

Earlier work this paper cites.

Maximum matching and a polyhedron with 0,1-vertices

J. Edmonds · 1965

Earlier work this paper cites.

Paths, trees, and flowers

J. Edmonds · 1965

Earlier work this paper cites.

An exact estimate of an algorithm for fnding a maximum flow, applied to the problem “on representatives”

A. V. Karzanov · 1971

Earlier work this paper cites.

An n 5 / 2 n^{5/2} algorithm for maximum matching in bipartite graphs

J. Hopcroft and R. M. Karp · 1973

Earlier work this paper cites.

Efficiency of a good but not linear set union algorithm

R. E Tarjan · 1975

Cited alongside, same era.

The complexity of computing the permanent

L.G. Valiant · 1979

Cited alongside, same era.

An O ⁡ ( V ​ E ) {O}(\sqrt{V}{E}) algorithm for finding maximum matching in general graphs

S. Micali and V. V. Vazirani · 1980

Cited alongside, same era.

A linear-time algorithm for a special case of disjoint set union

H. N. Gabow and R. E Tarjan · 1985

Cited alongside, same era.

Random generation of combinatorial structures from a uniform distribution

M.R. Jerrum, L.G. Valiant, and V.V. Vazirani · 1986

Cited alongside, same era.

Matching Theory

L. Lovász and M.D. Plummer · 1986

Cited alongside, same era.

A new approach to maximum matchings in general graphs

N. Blum · 1990

Later among the works it cites.

Faster scaling algorithms for general graph matching problems

H. N. Gabow and R. E Tarjan · 1991

Later among the works it cites.

A theory of alternating paths and blossoms for proving correctness of the O ⁡ ( V ​ E ) {O}(\sqrt{V}{E}) general graph maximum matching algorithm

Original

V. V. Vazirani · 1994

Later among the works it cites.

Maximum skew-symmetric flows and matchings

A. V. Goldberg and A. V. Karzanov · 2004

Later among the works it cites.

Maximum matchings via gaussian elimination

M. Mucha and P. Sankowski · 2004

Later among the works it cites.

Set-merging for the MV matching algorithm

H. N. Gabow · 2013

Closest in time.