The Connected p-Center Problem with Extension

Authors

William Chung-Kung Yen ⁰, Chien-Tsai Chen

Corresponding Author

William Chung-Kung Yen

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.