A linear-time algorithm for the center problem in weighted cycle graphs (Q6551721)

The authors give an $O(n)$-time algorithm for the discrete and continuous weighted center problem on cycle graphs with $n$ vertices. Their algorithm improves upon the best-known algorithm by \textit{M. B. Rayco} et al. [Comput. Oper. Res. 26, No. 10--11, 1113--1124 (1999; Zbl 0940.90064)] that takes $O(n\log n)$ time. Furthermore, it is optimal for the weighted center problem of cycle graphs. Their approach is completely different from the ones already available in the literature. For a cycle graph with $n$ vertices embedded in a unit circle, they define the dominating interval of a vertex $v$ with respect to a subset $W$ of vertices as the set of points in $S$ whose farthest vertex is $v$ among the vertices in $W$. A vertex $w$ in $W$ is active in $W$ if the dominating interval of $w$ with respect to $W$ is not empty. Then they show that the weighted center can be computed using the active vertices in $V$ and their dominating intervals. The main algorithmic contribution lies in computing the sequence of active vertices in $V$ in $O(n)$ time. Compared to the previous algorithm, their algorithm is simple, straightforward to implement, and robust.