Computing the center of uncertain points on cactus graphs

In this paper, we consider the (weighted) one-center problem of uncertain points on cactus graphs. Given are a cactus graph G and a set of n uncertain points. Each uncertain point has m possible locations on G with probabilities and a non-negative weight. The (weighted) one-center problem aims to compute a point (the center) x* on G to minimize the maximum (weighted) expected distance from x* to all uncertain points. No previous algorithms are known for this problem. In this paper, we propose an O(|G|+mnlogmn)-time algorithm for solving it. Since the input size is O(|G|+mn), our algorithm is almost optimal.