The Connected p-Center Problem with Extension

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)

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  -