Many facility location problems are modeled as optimization problems on graphs. We consider the following facility location problem. Given a graph G=(V, E) with N vertices and M edges, the k-neighbor, r-dominating set ((k, r)-dominating set) problem is to determine the minimum cardinality set D⊆V such that, for every vertex u∈V–D the distance between vertex u and at least k vertices in D is less than or equal to r. If we impose the condition that the graph induced by vertices in D should be connected, then the set D is a connected (k, r)-dominating set; if for each vertex in D there exists another vertex in D at a distance at most r, then the set D is a total(k, r)-dominating set; and if for each vertex in D there exists another vertex in D adjacent to it, then the set D is a reliable (k,r)-dominating set. In this paper, we present algorithms which run in O(k·N) time for solving the above problems on interval graphs, given its interval representation in sorted order. For the value of r=1, our algorithms have a time-complexity of O(min(kN, M)).
