The Connected p-Center Problem with Extension
Authors
William Chung-Kung Yen 0, Chien-Tsai Chen
Corresponding Author
William Chung-Kung Yen
0Professor, Dept. of Information Management, Shih Hsin Univ.
Available Online undefined NaN.
- DOI
- https://doi.org/10.2991/jcis.2006.216How to use a DOI?
- Keywords
- connected p-center, induced subgraph, NP-Hard, bipartite graph, tree, forbidden vertex
- Abstract
- Let G(V, E, W) be a graph n vertices and m edges, where each edge e is associated with a positive distance W(e). The traditional p-Center problem is to locate some kind of facilities at p vertices of G to minimize the maximum distance between any vertex and its nearest facility. This paper proposes a practical constraint: the subgraph induced by the p facility vertices must be connected and the problem is called the Connected p-Center problem. We show that the problem on bipartite graphs is NP-Hard, but O(n)-time solvable on trees. After then, the algorithmic result on trees is extended to the situation that some vertices in V cannot be selected as facility vertices.
- Open Access
- This is an open access article distributed under the CC BY-NC license.
Cite this article
TY - CONF AU - William Chung-Kung Yen AU - Chien-Tsai Chen PY - NaN/NaN DA - NaN/NaN TI - The Connected p-Center Problem with Extension BT - 9th Joint International Conference on Information Sciences (JCIS-06) PB - Atlantis Press UR - https://doi.org/10.2991/jcis.2006.216 DO - https://doi.org/10.2991/jcis.2006.216 ID - YenNaN/NaN ER -