Computation of Inverse 1 -Center Location Problem on the Weighted Trees

Abstract

Let r be a tree with (" + 1 ) vertices and # edges with positive edge weights. The inverse 1 -center problem on an edge weighted tree consists in changing edge weights at minimum cost so that a pre-specified vertex becomes the 1-center. In the context of location problems Cai et al. [9] proved that the inverse 1-center location problem with edge length modification on general unweighted directed graphs is NP-hard, while the underlying center location problem is solvable in polynomial time. Alizadeh et al. [1] have designed an algorithm for inverse 1 -center location problem with edge length augmentation on trees in a(" log ") time, using a set of suitably extended AVL-search trees. In [2], Alizadeh et al. have designed a combinatorial algorithm for inverse absolute on trees in a(772) time when topo|ogy not allowed and °("2J.) time when topology allowed. In this paper, we present an optimal algorithm to find an inverse 1-center location on the weighted trees with (" + 1 ) vertices and " edges, where the edge weights can be changed within certain bounds. The time complexity of our proposed algorithmis°("),if T is traversed in a depth-first-search marmer