K-Median Problem on Graph

In past decades there has been a tremendous growth in the literature on location problems. However, among the myriad of formulations provided, the simple plant location problem and the k-median problem have played a central role. This phenomenon is due to the fact that both problems have a wide range of real-world applications, and a mathematical formulation of these problems as an integer program has proven very fruitful in the derivation of solution methods. In this paper we investigate the k-median problem defined on a graph. That is, each point represents a vertex of a graph