QA291 : Interval graph and its application
Thesis > Central Library of Shahrood University > Mathematical Sciences > MSc > 2015
Authors:
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
Keeping place: Central Library of Shahrood University
Visitor:
Keeping place: Central Library of Shahrood University
Visitor: