TY - GEN
T1 - The Connected k-Vertex One-Center Problem on Graphs
AU - Zhang, Jingru
PY - 2025/1/1
Y1 - 2025/1/1
N2 - 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≤n, the problem aims to find a point on G so that the maximum (weighted) distance from it to k connected vertices on 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(mnlognlogmn+m2lognlogmn)-time algorithm is proposed for the weighted case, and an O(mnlogn)-time algorithm is presented for the unweighted case, provided that the distance matrix is given. When G is a tree graph, we give an O(nlog2nlogk)-time algorithm for the weighted case and improve it to O(nlog2n) for the unweighted case.
AB - 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≤n, the problem aims to find a point on G so that the maximum (weighted) distance from it to k connected vertices on 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(mnlognlogmn+m2lognlogmn)-time algorithm is proposed for the weighted case, and an O(mnlogn)-time algorithm is presented for the unweighted case, provided that the distance matrix is given. When G is a tree graph, we give an O(nlog2nlogk)-time algorithm for the weighted case and improve it to O(nlog2n) for the unweighted case.
KW - Algorithms
KW - Connectivity
KW - Data Structures
KW - Facility Locations
KW - Graphs
KW - k-Vertex One-Center
UR - https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=86000196964&origin=inward
UR - https://www.scopus.com/inward/citedby.uri?partnerID=HzOxMe3b&scp=86000196964&origin=inward
U2 - 10.1007/978-981-96-2845-2_26
DO - 10.1007/978-981-96-2845-2_26
M3 - Conference contribution
SN - 9789819628445
VL - 15411 LNCS
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 409
EP - 423
BT - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
A2 - Nakano, Shin-ichi
A2 - Xiao, Mingyu
PB - Springer Science and Business Media Deutschland GmbH
CY - deu
T2 - 19th International Conference and Workshops on Algorithms and Computation, WALCOM 2025
Y2 - 28 February 2025 through 2 March 2025
ER -