Many facility location problems are modeled as optimization problems o
n graphs. We consider the following facility location problem. Given a
graph G = (V, E) with N vertices and M edges, the k-neighbor, r-domin
ating set ((k, r)-dominating set) problem is to determine the minimum
cardinality set D subset-or-equal-to V such that, for every vertex u i
s-an-element-of V - D the distance between vertex u and at least k ver
tices 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, o
ur algorithms have a time-complexity of O(min(kN, M)).