Networking and Communication Engineering

Abstract

Let T be a tree with (1)n vertices and n 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 un-weighted 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 (log)Onn 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 2()On time when topology not allowed and 2()Onr 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)n vertices and n edges, where the edge weights can be changed within certain bounds. The time complexity of our proposed algorithm is ()On, if T is traversed in a depth-first-search manner.

Keywords

Full Text