The k-center problem of uncertain points on graphs

• The k-center problem of uncertain points on undirected graphs is studied. • The first exact algorithm is proposed for the problem with k ≥ 3. • An O ( | E | 2 m 2 n log | E | m n log m n ) − t i m e algorithm is given for the problem with k = 2 . • An O ( | E | m n log m n ) − t i m e algorithm is developed for the one-center case. In this paper, we study the k -center problem of uncertain points on a graph. Given are an undirected simple graph G = ( V , E ) and a set P of n uncertain points where each uncertain point with a non-negative weight has m possible locations on G each associated with a probability. The problem aims to find k centers (points) on G so as to minimize the maximum weighted expected distance of uncertain points to their own expected closest centers. No previous work exist for the k -center problem of uncertain points on undirected graphs. We propose exact algorithms that solve respectively the case of k = 2 in O (| E | 2 m 2 n log | E | mn log mn ) time and the problem with k ≥ 3 in O ( min { | E | k m k n k + 1 k log | E | m n log m , | E | k n k 2 m k 2 2 log | E | m n } ) time, provided with the distance matrix of G . In addition, an O (| E | mn log mn )-time algorithmic approach is given for the one-center case.