Finding Connected p-Centers on Interval Graphs

Abstract

Let G(V, E) be an undirected and connected simple graph with n vertices. A positive weight 1w(v) is ociated to each vertex v and a positive length 2w(e) is ciated with each edge e. Given an integer p ≥ 1, the fundamental p-Center problem is to locate a p-vertex set Q of G for the establishment of facilities. Minimizing the maximum weighted distance for each vertex v in V – Q to its nearest facility site is the most important criteria. This paper focuses on the issue of finding connected p-centers on graphs, called the Connected p-Center problem (the CpC problem), which is a new practical variant from the p-Center problem. A p-center Q is connected if the subgraph induced by the vertices in Q is connected. Under the assumption that the clique path is given, this paper designs an O(n)-time algorithm for the CpC problem on interval graphs with 1w(v) = 1, for all tices v, and 2w(e) = 1, for all edges e.