Please use this identifier to cite or link to this item: `http://inet.vidyasagar.ac.in:8080/jspui/handle/123456789/5858`
 Title: Inverse 1-Center and Minimum Average Distance Problems on Graphs Authors: Pal, MadhumangalMondal, SukumarJana, Biswanath Keywords: Tree - NetworksInverse 1 - Centre LocationInterval graphsMAD TreesSpanning TreesAlgorithms - Complexity Issue Date: 19-Feb-2021 Publisher: Vidyasagar University, Midnapore, West Bengal, India, Abstract: Graph theory has undergone a powerful development, since its beginning in the 18th century. Many real-life problems can be modelled by graph-theoretic problems. The graph problems are usually NP-hard and hence there is no efficient algorithm for solving them, unless P = NP. One way to overcome this hardness is to solve the problems when restricted to special classes of graphs. The intersection graphs are the most useful graph classes and interval, circular-arc, permutation and trapezoid graphs are major subclasses of intersection graphs for which several NP-complete problems can be solved in polynomial time. The main focus of this work is the study of some important problems on interval, permutation, trapezoid and circular-arc graphs which are the very important subclasses of the intersection graphs. In Chapter 1, basic definitions, recognitions, applications, survey, etc. of the interval, permutation, trapezoid graphs, circular-arc graphs and related graphs are discussed. In Chapter 2, computation of inverse 1-center location problem on the weighted trees is studied. Let T be a tree with (n + 1) vertices and n edges with positive edge weights. The inverse 1-center problem on an edge weighted tree consists in changing edge weights at minimum cost so that a pre-specified vertex becomes the 1-center. In this chapter, an optimal algorithm is designed to find an inverse 1-center location on the weighted trees whose number of vertices and edges are (n + 1) and n, and the edge weights can be changed within certain bounds. Chapter 3 is devoted for solving inverse 1-center location problem on the weighted interval graphs and construction of minimum average distance tree on fuzzy interval graphs. Let T1a be the tree corresponding to the weighted interval graph. In an inverse 1-center location problem the parameter of an interval tree Tw corresponding to the weighted interval graph, like vertex weights have to be modified at minimum total cost such that a pre-specified vertex s E V becomes the 1-center of the interval graph G. Here an O(n) time algorithm is designed to find an inverse 1-center location problem on the weighted tree 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. Besides these, an O(n)-time algorithm is also presented to compute the average distance of a graph G (with finite number of nodes and edges). This is the average of the distances over all unordered pairs of nodes. A minimum average distance spanning tree (MADST, in short) of G is a spanning tree of G having minimum average distance. Further, an O(n2 )-time algorithm is designed to determine a MADST on the fuzzy interval graph, where n is the cardinality of the node set of given graph. In Chapter 4, the methods of computation of minimum average distance tree and inverse 1-center location problem on the circular-arc graphs are described. The average distance of a finite graph G is the average of the distances over all unordered pairs of vertices. A minimum average distance spanning tree of G is a spanning tree of G with minimum average distance. Such a tree is sometimes referred to as a minimum routing cost spanning tree. In this chapter, an efficient algorithm is designed to compute a minimum average distance spanning tree on circular-arc graph which takes 0(n2 ) time, where n is the number of vertices of the graph. Also, in thls chapter, an optimal algorithm is designed to find an inverse 1-center location on the weighted tree corresponding to the weighted circular-arc graph, where the node weights can be modified within certain bounds. The time complexity of the proposed algorithm is 0(n}, where n is the number of vertices. Chapter 5 discusses methods of computation of a minimum average distance tree and in­ verse 1-center location problem on permutation graphs and on weighted permutation graphs, respectively. The average distance µ( G) of a finite graph G is the average of the distances over all unordered pairs of vertices. A minimum average distance spanning tree of G is a spanning tree of G with minimum average distance. In thls chapter, an efficient algorithm is designed to compute a minimum average distance spanning tree on permutation graphs in O(n2 ) time, where n is the number of vertices of the graph. Also, an O(n 2 }-time algorithm is presented to compute an inverse 1-center of the weighted permutation graph, where the node weights can be modified under some certain restrictions. The time complexity of the proposed algorithm is 0(n). The sixth chapter presents an optimal algorithm for computation of inverse 1-center lo­cation problem on the weighted trapezoid graphs. Let TTRP 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 E TTRP· A vertex with minimum eccentricity in the tree TTRP is called the 1-center of that tree. In an inverse 1-center location problem the parameter of the tree TTRP corresponding to the weighted trapezoid graph, like vertex weights have to be modified at minimum total cost such that a pre-specified vertex s E V becomes the 1-center of the trapezoid graph G. In thls chapter, an optimal algorithm is presented to find an inverse 1-center location on the weighted tree TTRP corresponding to the weighted trapezoid graph, where the vertex weights can be changed within certain bounds. The time complexity of the proposed algorithm is O(n). Finally, Chapter 7 contains some concluding remarks and scopes of further research on the problems that have been studied in the thesis. URI: http://inet.vidyasagar.ac.in:8080/jspui/handle/123456789/5858 Appears in Collections: Applied Mathematics with Oceanology and Computer Programming - Ph.D

Files in This Item:
File Description SizeFormat