TR-2002-06

A magyar módszer és általánosításai (The Hungarian method and its extensions; in Hungarian)

András Frank

Published in:
Szigma 33 (2002) 13-44.

One of the earliest appearance of a special form of the linear programming duality theorem is E. Egerváry's classical result on the maximum weight of a perfect matching in a complete bipartite graph. Its elegant proof gave rise to an efficient algorithm called the Hungarian Method. The basic principles of the procedure has been generalized in several directions such as the maximum weight matching problem in nonbipartite graphs, the weighted matroid intersection and the submodular flow problem. In the present work we overview these extensions of the Hungarian Method. As a new contribution, a short proof is given for the weigth-splitting version of the weighted matroid intersection theorem.

Bibtex entry:

@techreport{egres-02-06,

AUTHOR	=	{Frank, Andr{\'a}s},
TITLE	=	{A magyar módszer és általánosításai (The Hungarian method and its extensions; in Hungarian)},
NOTE	=	{{\tt egres.elte.hu}},
INSTITUTION	=	{Egerv{\'a}ry Research Group, Budapest},
YEAR	=	{2002},
NUMBER	=	{TR-2002-06}

}