An optimal algorithm for an outerplanar facility location problem with improved time complexity

We consider a network facility location problem with unbounded production levels. This problem is NP-hard in the general case and is known to have an optimal solution with quadratic complexity on a tree network. We study the case of a network representable by an outerplanar graph, i.e., by a graph whose vertices belong to one (outer) face. This problem is known to have an optimal algorithm with time complexity $O(nm^3)$, where $n$ is the number of vertices and $m$ is the number of possible facility locations. Using some properties of outerplanar graphs (binary 2-trees) and the existence of an optimal solution with a family of centrally connected service domains, we obtain recurrence relations for the construction of an optimal algorithm with time complexity that is smaller by a factor of $\sqrt{m}$ than the time complexity of the earlier algorithm.