|
 Cybernetics and Systems Analysis /  Issue (2016, 52 (5))
Matsiy O.B.,
Morozov A.V.,
Panishev A.V.
A recurrent algorithm to solve weighted matching problem The well-known problem of weighted matching in an arbitrary graph H with n vertices is reduced to a matching problem for a bipartite graph with 2n vertices. The maximum matching of graph H with the minimum sum of weights of edges defined by matrix[cij]n is found in timeO (n3) after ordering, in non-descending order, the values above the main diagonal. © 2016, Springer Science+Business Media New York. Keywords: assignment problem, augmenting path, bipartite graph, matching, weighted matching problem, Combinatorial optimization, Assignment problems, Augmenting path, Bipartite graphs, matching, Weighted matching, Graph theory
Cite:
Matsiy O.B.,
Morozov A.V.,
Panishev A.V.
(2016). A recurrent algorithm to solve weighted matching problem. Cybernetics and Systems Analysis, 52 (5), 101-112. doi: https://doi.org/10.1007/s10559-016-9876-4 http://jnas.nbuv.gov.ua/article/UJRN-0000553521 [In Russian]. |
PDF
