Title: Computation of inverse 1-centre location problem on the weighted interval graphs
Authors: Biswanath Jana; Sukumar Mondal; Madhumangal Pal
Addresses: Department of Applied Mathematics with Oceanology and Computer Programming, Vidyasagar University, 721102, Midnapore, India ' Department of Mathematics, Raja N. L. Khan Women's College, Gope Palace, 721102 Paschim Medinipur, India ' Department of Applied Mathematics with Oceanology and Computer Programming, Vidyasagar University, 721102, Midnapore, India
Abstract: Let TIG 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 TIG 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 ∈ 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 TIG 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.
Keywords: tree-networks; centre location; 1-centre location; inverse 1-centre location; inverse optimisation; tree; interval graphs.
DOI: 10.1504/IJCSM.2017.10010016
International Journal of Computing Science and Mathematics, 2017 Vol.8 No.6, pp.533 - 541
Received: 18 Apr 2016
Accepted: 08 May 2017
Published online: 03 Jan 2018 *