Computation of inverse 1-center location problem on the weighted Permutation Graphs

Abstract

Let TP ER be the tree corresponding to the weighted permutation graph G = (V, E). The eccentricity e(v) of the vertex v is defined as the sum of the weights of the vertices from v to the vertex farthest from v ∈ TP ER. A vertex with minimum eccentricity in the tree TP ER is called the 1-center of that tree. In an inverse 1-center location problem the parameter of the tree TP ER corresponding to the weighted permutation graph G = (V, E), like vertex weights have to be modified at minimum total cost such that a pre-specified vertex s ∈ V becomes the 1-center of the permutation graph G. In this paper, we present an optimal algorithm to find an inverse 1- center location on the tree TP ER corresponding to the permutation graph G = (V, E), where the vertex weights can be changed within certain bounds. The time complexity of our proposed algorithm is O(n), where n is the number of vertices of the weighted permutation graph G.