The Connected k-Vertex One-Center Problem on Graphs
Fuente:
arXiv
Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866912196344152064 |
|---|---|
| author | Zhang, Jingru |
| author_facet | Zhang, Jingru |
| contents | We consider a generalized version of the (weighted) one-center problem on graphs. Given an undirected graph $G$ of $n$ vertices and $m$ edges and a positive integer $k\leq n$, the problem aims to find a point in $G$ so that the maximum (weighted) distance from it to $k$ connected vertices in its shortest path tree(s) is minimized. No previous work has been proposed for this problem except for the case $k=n$, that is, the classical graph one-center problem. In this paper, an $O(mn\log n\log mn + m^2\log n\log mn)$-time algorithm is proposed for the weighted case, and an $O(mn\log n)$-time algorithm is presented for the unweighted case, provided that the distance matrix for $G$ is given. When $G$ is a tree graph, we propose an algorithm that solves the weighted case in $O(n\log^2 n\log k)$ time with no given distance matrix, and improve it to $O(n\log^2 n)$ for the unweighted case. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_18001 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | The Connected k-Vertex One-Center Problem on Graphs Zhang, Jingru Data Structures and Algorithms We consider a generalized version of the (weighted) one-center problem on graphs. Given an undirected graph $G$ of $n$ vertices and $m$ edges and a positive integer $k\leq n$, the problem aims to find a point in $G$ so that the maximum (weighted) distance from it to $k$ connected vertices in its shortest path tree(s) is minimized. No previous work has been proposed for this problem except for the case $k=n$, that is, the classical graph one-center problem. In this paper, an $O(mn\log n\log mn + m^2\log n\log mn)$-time algorithm is proposed for the weighted case, and an $O(mn\log n)$-time algorithm is presented for the unweighted case, provided that the distance matrix for $G$ is given. When $G$ is a tree graph, we propose an algorithm that solves the weighted case in $O(n\log^2 n\log k)$ time with no given distance matrix, and improve it to $O(n\log^2 n)$ for the unweighted case. |
| title | The Connected k-Vertex One-Center Problem on Graphs |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2412.18001 |