УДК 519.161

Рекуррентный алгоритм решения задачи о взвешенном паросочетании

/ О.Б. Маций, А.В. Морозов, А.В. Панишев // Кибернетика и системный анализ. — 2016. — Том 52, № 5. — С. 101–112.

Известная задача о взвешенном паросочетании в произвольном графе H з n с вершинами сводится к одной из задач о паросочетании для двудольного графа с 2n вершинами. Максимальное паросочетание графа H з n с минимальной суммой весов ребер, заданных матрицей [c_ij]_n, находится за время O(n³) после упорядочения по неубыванию значений c_ij, расположенных над главной диагональю. Ил.: 6. Табл.: 0. Библиогр.: 4 назв.

Ключевые слова:

паросочетание, задача о взвешенном паросочетании, двудольный граф, увеличивающий путь, задача о назначениях.


ПОЛНЫЙ ТЕКСТ

Об авторе(ах):

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

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

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