Полиномиальный алгоритм решения задачи размещения на цепи с одинаковыми производственными мощностями предприятий

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