最大权完美匹配的“原始—对偶”算法

Primal-dual Algorithms for Max-weight Perfect Matching

给出了利用"互补松弛原理"以及"原始—对偶原理"在一个完全赋权二部图G=(X,Y,E,ω),ω≥0,|X|=|Y|=n中寻找最大权完美匹配的算法和过程.

In this paper, the detail and algorithrns for ma：dmum weight perfect matching in a complete weighted bipartite,G=（X,Y,E,ω）,ω≥0,｜X｜=｜Y｜=n,were studied. The main methods are complementary-slacknessa theorem and primal-dual algorithms.