УДК 519.161

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

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

Відома задача про зважену паросполуку в довільному графі H з n вершинами зводиться до однієї із задач про паросполуку для двочасткового графа з 2n вершинами. Максимальна паросполука графа H з мінімальною сумою ваг ребер, заданих матрицею [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