Uniform-cost inverse absolute and vertex center location problems with edge length variations on trees

This article considers the inverse absolute and the inverse vertex 1-center location problems with uniform cost coefficients on a tree network TT with n+1n+1 vertices. The aim is to change (increase or reduce) the edge lengths at minimum total cost with respect to given modification bounds such that a prespecified vertex ss becomes an absolute (or a vertex) 1-center under the new edge lengths. First an O(nlogn)O(nlogn) time method for solving the height balancing problem with uniform costs is described. In this problem the height of two given rooted trees is equalized by decreasing the height of one tree and increasing the height of the second rooted tree at minimum cost. Using this result a combinatorial O(nlogn)O(nlogn) time algorithm is designed for the uniform-cost inverse absolute 1-center location problem on tree TT. Finally, the uniform-cost inverse vertex 1-center location problem on TT is investigated. It is shown that the problem can be solved in O(nlogn)O(nlogn) time if all modified edge lengths remain positive. Dropping this condition, the general model can be solved in O(rvnlogn)O(rvnlogn) time where the parameter rvrv is bounded by ⌈n/2⌉⌈n/2⌉. This corrects an earlier result of Yang and Zhang.