| Abstract: | Summary This paper deals with the problem of finding the maximum matching of a weighted graph, having the minimum cost. This problem is solved via a branch and bound algorithm, derived directly fromLand andDoig's technique. The linear programming problem associated with each step of the procedure is solved through a primal-dual algorithm.
Zusammenfassung Diese Arbeit beschäftigt sich mit demmatching problem. In einem gewichteten Graphen ist dasmaximal matching mit minimalen Kosten gesucht. Zur Lösung wird ein vonLand undDoig beschriebener Branch-and-Bound-Algorithmus verwendet. Das sich je Iterationsschritt ergebende LP-Problem wird mit einem Primal-Dual-Algorithmus gelöst.
The authors are with the Laboratory of Automatic Control, Istituto di Elettrotecnica ed Elettronica, Politecnico di Milano, I-20133 Milano, Piazza Leonardo da Vinci, 32. |
