On the Solution Value of the Continuous p-Center Location Problem on a Graph

Let G = (V, E) be an undirected graph with positive edge lengths. Let r_p denote the solution value to the continuous p-center location problem on G. We prove that r_p is of the form r_p = T/2q, where T is the length of an Euler tour of a subgraph of G which belongs to one of four possible types, and q is an integer, 1 ≤ q ≤ 2p. We also discuss algorithmic implications of this result.