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.088962

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 *

Full-text access for editors Access for subscribers Purchase this article Comment on this article

 

Return to top