Computing the Center of Uncertain Points on Cactus Graphs
Document Type
Article
Publication Date
4-2026
Publication Title
Theoretical Computer Science
Abstract
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| + mn log mn)-time algorithm for solving it. Since the input size is O(|G| + mn), our algorithm is almost optimal.
DOI
10.1016/j.tcs.2026.115761
Recommended Citation
Hu, Ran; Kanani, Divy H.; and Zhang, Jingru, "Computing the Center of Uncertain Points on Cactus Graphs" (2026). Computer Science Faculty Publications. 10.
https://engagedscholarship.csuohio.edu/encs_facpub/10
Volume
1067
