QA291 : Interval graph and its application
Thesis > Central Library of Shahrood University > Mathematical Sciences > MSc > 2015
Authors:
Omolbanin Rabiey [Author], Sadegh Rahimi Shearbaf Moghaddas[Supervisor]
Abstarct: Interval graph is a very important subclass of intersection graphs and perfect graphs. It has many applications in different real life situations. In the first chapter, we present some concepts and notations which we use in the future chpters. In the second chapters we give some hereditary properties and characterizations proposed by Gilmore-Hoffman and Fulkerson-Gross and Lekkerkerker-Boland that are useful to recognize an Interval graph. In the next chapter the data structure, interval tree, is introduced for interval graph. We solve tree 3-spanner, shortest distances between any two vertices, the diameter and center of interval graph with using of interval tree. An O(n) time algorithm is presented to computing for them. In the next chapter with brief review of fuzzy sets we define the fuzzy intersection graph of a family of fuzzy sets. And we show that the characterization of Interval graphs by Gilmore-Hoffman naturally extends to fuzzy Interval graphs while that of Fulkerson-Gross does not. In the last chapter aims to find a solution to the ”maximum weight 1 colouring” (MW1C) for an Interval graphs with Interval weight. And an algorithm is presented to solve this problem using O(n) time.
Keywords:
#Interval graph #Interval tree #All-pairs shortest paths #Tree 3-spanner #Diameter #Interval Fuzzy graph Link
Keeping place: Central Library of Shahrood University
Visitor: