Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | https://arxiv.org/abs/2504.14803 |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866912774972506112 |
|---|---|
| author | Xu, Haitao Zhang, Jingru |
| author_facet | Xu, Haitao Zhang, Jingru |
| contents | In this paper, we study the $k$-center problem of uncertain points on a graph. Given are an undirected graph $G = (V, E)$ and a set $\mathcal{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 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|^2m^2n\log |E|mn\log mn )$ time and the problem with $k\geq 3$ in $O(\min\{|E|^km^kn^{k+1}k\log |E|mn\log m, |E|^kn^\frac{k}{2}m^\frac{k^2}{2}\log |E|mn\})$ 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_14803 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | The k-Center Problem of Uncertain Points on Graphs Xu, Haitao Zhang, Jingru Data Structures and Algorithms In this paper, we study the $k$-center problem of uncertain points on a graph. Given are an undirected graph $G = (V, E)$ and a set $\mathcal{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 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|^2m^2n\log |E|mn\log mn )$ time and the problem with $k\geq 3$ in $O(\min\{|E|^km^kn^{k+1}k\log |E|mn\log m, |E|^kn^\frac{k}{2}m^\frac{k^2}{2}\log |E|mn\})$ 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. |
| title | The k-Center Problem of Uncertain Points on Graphs |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2504.14803 |