EN|RU

Том 18, номер 4, 2011 г., Стр. 49-65

УДК 519.854
Забудский Г. Г., Лагздин А. Ю.
Полиномиальные алгоритмы решения минимаксной квадратичной задачи о назначениях на сетях

Аннотация:
Рассматривается квадратичная задача о назначениях с минимаксным критерием в терминах теории графов: необходимо разместить вершины графа в узлы сети таким образом, чтобы максимальная связь между смежными вершинами была минимальной. Предлагаются полиномиальные алгоритмы решения этой задачи на специальных типах сетей.
Ил. 7, библиогр. 13.

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

Забудский Геннадий Григорьевич 1
Лагздин Артём Юрьевич 1

1. Омский филиал Института математики им. С. Л. Соболева СО РАН,
ул. Певцова, 13, 644099 Омск, Россия
е-mail: zabudsky@o_m.oscsbras.ru, art.lagzdin@gmail.com

Статья поступила 31 мая 2010 г.
Исправленный вариант — 20 июня 2011 г.

 © Институт математики им. С. Л. Соболева, 2015