Computation of inverse 1-centre location problem on the weighted interval graphs (Q2224231)

Summary: Let \(T_{IG}\) be the tree corresponding to the weighted interval graph \(G = (V,E)\). In an inverse 1-centre location problem the parameter of an interval tree \(T_{IG}\) corresponding to the weighted interval graph \(G = (V,E)\), like vertex weights have to be modified at minimum total cost such that a pre-specified vertex \(s \in V\) becomes the 1-centre of the interval graph \(G\). In this paper, we present an \(O(n)\) time algorithm to find an inverse 1-centre location problem on the weighted tree \(T_{IG}\) corresponding to the weighted interval graph, where the vertex weights can be changed within certain bounds and \(n\) is the number of vertices of the graph \(G\).