EN|RU

Том 18, номер 5, 2011 г., Стр. 3-10

УДК 519.718
Визинг В. Г.
Многокритериальные задачи на графах с максиминным критерием

Аннотация:
Рассматриваются r-критериальные задачи для r-взвешенных графов (r ≥ 2). Подграфы определённого вида называются допустимыми. Решение задачи состоит в выборе оптимального по Парето допустимого подграфа из полного множества альтернатив (ПМА). Основной результат состоит в следующем. Предположим, что один из критериев, обозначаемый MAXMIN, требует максимизации минимального первого веса рёбер допустимого подграфа и имеется эффективная процедура, строящая ПМА для (r − 1)-критериальной задачи без этого максиминного критерия. Тогда эффективно строится ПМА для исходной r-критериальной задачи.
Библиогр. 11.

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

Визинг Вадим Георгиевич 1
1. ул. Варненская, 18/2, кв. 26, 65070 Одесса, Украина
е-mail: vizing@paco.net

Статья поступила 17 мая 2011 г.

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