@inproceedings{36a6675f202b4dbdacca305152fbb34c,
title = "Computing the Center of Uncertain Points on Cactus Graphs",
abstract = "In this paper, we consider the (weighted) one-center problem of uncertain points on a cactus graph. 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 algorithm is known for this problem. In this paper, we propose an O(| G| + mnlog mn) -time algorithm for solving it. Since the input is O(| G| + mn), our algorithm is almost optimal.",
keywords = "Algorithms, Cactus Graph, One-Center, Uncertain Points",
author = "Ran Hu and Kanani, \{Divy H.\} and Jingru Zhang",
year = "2023",
month = jan,
day = "1",
doi = "10.1007/978-3-031-34347-6\_20",
language = "English",
isbn = "9783031343469",
volume = "13889 LNCS",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Science and Business Media Deutschland GmbH",
pages = "233--245",
editor = "Sun-Yuan Hsieh and Ling-Ju Hung and Chia-Wei Lee",
booktitle = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
note = "34th International Workshop on Combinatorial Algorithms, IWOCA 2023 ; Conference date: 07-06-2023 Through 10-06-2023",
}