We consider the absolute p-center problem on a general network and propose a spanning tree approach which is motivated by the fact that the problem is NP-hard on general networks but solvable in polynomial time on trees. We ®rst prove that every connected network possesses a spanning tree whose p-center solution is also a solution for the network under consideration. Then we propose two classes of spanning trees that are shortest path trees rooted at certain points of the network. We give an experimental study, based on 1440 instances, to test how often these classes of trees include an optimizing tree. We report our computational results on the performance of both types of trees. Ó
REF proposed a spanning tree approach on cyclic networks.
A SPANNING TREE APPROACH TO THE ABSOLUTE P-CENTER PROBLEM.
Location Science
Mathematics