Computation of Inverse 1-Center Location Problem on The Weighted Trapezoid Graphs

Abstract

TT RP be the tree corresponding to the weighted trapezoid 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 ∈ TT RP . A vertex with minimum eccentricity in the tree TT RP is called the 1-center of that tree. In an inverse 1-center location problem, the parameter of the tree TT RP corresponding to the weighted trapezoid 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 trapezoid graph G. In this paper, we present an optimal algorithm to find an inverse 1-center location on the weighted tree TT RP corresponding to the weighted trapezoid 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 trapezoid graph G.