A B C D E F G H I J K L M N O P Q R S T U V W X Y Z All
Pal, Madhumangal
- Computation of Inverse 1-Center Location Problem on the Weighted Trees
Authors
1 Vidyasagar University, Midnapore -721 102, IN
2 Department of Mathematics, Raja N. L. Khan Women's College, Gope Palace, Paschim Medinipur-721 102, IN
3 Department of Applied Mathematics with Oceanology and Computer Programming, Vidyasagar University, Midnapore-721 102, IN
Source
Networking and Communication Engineering, Vol 4, No 2 (2012), Pagination: 70-75Abstract
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.