Inverse 1-center location problems with edge length augmentation on trees

摘要

This paper considers the inverse 1-center location problem with edge length augmentation on a tree network T with n + 1 vertices. The goal is to increase the edge lengths at minimum total cost subject to given modification bounds such that a predetermined vertex s becomes an absolute 1-center under the new edge lengths. Using a set of suitably extended AVL-search trees we develop a combinatorial algorithm which solves the inverse 1-center location problem with edge length augmentation in O(n log n) time. Moreover, it is shown that the problem can be solved in O(n) time if all the cost coefficients are equal. [PUBLICATION ABSTRACT]