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

The Connected p-Center Problem with Extension

Authors
William Chung-Kung Yen1, Chien-Tsai Chen
1Professor, Dept. of Information Management, Shih Hsin Univ.
Corresponding Author
William Chung-Kung Yen
Available Online October 2006.
DOI
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.

Copyright
© 2006, the Authors. Published by Atlantis Press.
Open Access
This is an open access article distributed under the CC BY-NC license (http://creativecommons.org/licenses/by-nc/4.0/).

Download article (PDF)

Volume Title
Proceedings of the 9th Joint International Conference on Information Sciences (JCIS-06)
Series
Advances in Intelligent Systems Research
Publication Date
October 2006
ISBN
978-90-78677-01-7
ISSN
1951-6851
DOI
10.2991/jcis.2006.216How to use a DOI?
Copyright
© 2006, the Authors. Published by Atlantis Press.
Open Access
This is an open access article distributed under the CC BY-NC license (http://creativecommons.org/licenses/by-nc/4.0/).

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  - Proceedings of the 9th Joint International Conference on Information Sciences (JCIS-06)
PB  - Atlantis Press
SP  - 425
EP  - 428
SN  - 1951-6851
UR  - https://doi.org/10.2991/jcis.2006.216
DO  - 10.2991/jcis.2006.216
ID  - Yen2006/10
ER  -