The Two-Center Problem of Uncertain Points on Trees

In this paper, we consider the (weighted) two-center problem of uncertain points on a tree. Given are a tree $T$ and a set $\text{calP}$ of $n$ (weighted) uncertain points each of which has $m$ possible locations on $T$ associated with probabilities. The goal is to compute two points on $T$, i.e., two centers with respect to $\text{calP}$, so that the maximum (weighted) expected distance of $n$ uncertain points to their own expected closest center is minimized. This problem can be solved in $O(\mathrm{\mid }T\mathrm{\mid }+n^2\log n\log mn+mn{\log }^{2}mn\log n)$ time by the algorithm for the general $k$-center problem. In this paper, we give a more efficient and simple algorithm that solves this problem in $O(\mathrm{\mid }T\mathrm{\mid }+mn\log mn)$ time.