Эффективный алгоритм решения двухэтапной задачи размещения на древовидной сети

Рассматривается двухэтапная задача размещения производства на древовидной сети при условии, что затраты на транспортировку единицы продукции из пункта в пункт равны сумме длин рёбер в цепи, соединяющей эти пункты. Предложен алгоритм для точного решения данной задачи с трудоёмкостью $O(nm^3)$, где $n$ – число пунктов спроса конечного продукта, $m$ – ограничение сверху на число возможных пунктов размещения производства каждого этапа. Ил. 3, библиогр. 7.