UDC 519.161

A recurrent algorithm to solve weighted matching problem

/ O.B. Matsiy, A.V. Morozov, A.V. Panishev // Kibernetika i sistemnyi analiz. — 2016. — Vol. 52, N 5. — P. 101–112.

The well-known problem of weighted matching in an arbitrary graph H з n with n vertices is reduced to a of matching problem for a bipartite graph with 2n vertices. The maximum matching of graph H з n with the minimum sum of weights of edges specified by matrix [c_ij]_n is found in time O(n³) after ordering the values c_ij above the main diagonal in non-decreasing order. Figs: 6. Tabl.: 0. Refs: 4 titles.

Keywords:

matching, the problem of the weighted matching, bipartite graph, increasing path, the assignment problem.


FULL TEXT

Author(s):

Маций Ольга Борисовна, ассистентка Харьковского национального автомобильно-дорожного университета,
e-mail: om21@mail.ru

Морозов Андрей Васильевич, кандидат техн. наук, доцент, декан Житомирского государственного технологического университета,
e-mail: morozov.andriy@gmail.com

Панишев Анатолий Васильевич, доктор техн. наук, профессор, заведующий кафедрой Житомирского государственного технологического университета,
e-mail: pzs.ztu@gmail.com