LAUSR

We consider the facility location problem of locating a set $$X_p$$Xp of p facilities (resources) on a network (or a graph) such that the subnetwork (or subgraph) induced by the selected set $$X_p$$Xp is connected. Two problems on a block graph G are proposed: one problem is to minimizes the sum of its weighted distances from all vertices of G to $$X_p$$Xp, another problem is to minimize the maximum distance from each vertex that is not in $$X_p$$Xp to $$X_p$$Xp and, at the same time, to minimize the sum of its distances from all vertices of G to $$X_p$$Xp. We prove that the first problem is linearly solvable on block graphs with unit edge length. For the second problem, it is shown that the set of Pareto-optimal solutions of the two criteria has cardinality not greater than n, and can be obtained in $$O(n^2)$$O(n2) time, where n is the number of vertices of the block graph G.