Точный алгоритм решения внешнепланарной задачи размещения с улучшенной временной сложностью

Рассматривается сетевая задача размещения с неограниченными объемами производства. В общем случае задача $NP$-трудна. Известно, что задача точно решается с квадратичной трудоемкостью на древовидной сети. В статье исследуется случай сети, представляемой внешнепланарным графом, т. е. графом, все вершины которого принадлежат одной (внешней) грани. Для точного решения рассматриваемой задачи был известен алгоритм с временной сложностью $O(n m^3)$, где $n$ — число вершин, $m$ — число возможных мест размещения предприятий. При использовании некоторых свойств внешнепланарных графов (бинарных 2-деревьев) и учете существования оптимального решения с совокупностью центрально связных областей обслуживания получены рекуррентные соотношения, позволяющие построить точный алгоритм, решающий задачу с уменьшенной в $\sqrt{m}$ раз временной сложностью.