Upgrading the 1-center problem with edge length variables on a tree

This paper discusses upgrading the 1-center problem on networks, which tries to change the lengths of the edges within certain bounds and find the best place for 1-center with respect to the new lengths so that the objective value is minimized. As this problem is NP-hard on general graphs, the problem is considered where the underlying graph is a tree. It is mentioned that this problem is solvable in polynomial time by solving a series of linear programs. A combinatorial algorithm with On2log(n) time complexity is proposed for the equal cost case, where n is the number of vertices of the tree. It is also shown that the problem is solvable in On2log(n)2 time on an unweighted tree, i.e., all vertex weights are equal to one, but the costs are arbitrary.