Том 7, серия 2, номер 1, 2000 г., Стр. 3-8

УДК 519.87+519.854.33
И. П. Вознюк
Задача размещения пунктов производства на два-дереве с ограниченными пропускными способностями коммуникаций

Аннотация:
Рассмотрена задача о наилучшем размещении пунктов производства в вершинах сети с ограниченными пропускными способностями коммуникаций. Показано, что если сеть является два-деревом, то задача решается методом динамического программирования за время $O(nb^4)$ при объеме памяти $O(nb^2)$, где $n$ – число вершин сети, $b$ –суммарный объем спроса.
Библиогр. 8.

Вознюк И. П. ¹
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
е-mail: deplab® math.nsc.ru

Статья поступила 18 февраля 1999 г.
Исправленный вариант — 9 февраля 2000 г.