9th Joint International Conference on Information Sciences (JCIS-06)

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 October 2006.
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.

Download article (PDF)

Proceedings
9th Joint International Conference on Information Sciences (JCIS-06)
Part of series
Advances in Intelligent Systems Research
Publication Date
October 2006
ISBN
978-90-78677-01-7
DOI
https://doi.org/10.2991/jcis.2006.216How to use a DOI?
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  - 2006/10
DA  - 2006/10
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  - Yen2006/10
ER  -