Search

Nowadays, graph algorithms have been applied to many practical issues such as networking, very large-scale integration (VLSI), and transport systems, etc. Constructing an algorithm to find a maximum independent set (MIS) is one of the first NP-Hard problems which have been studied for a long time. Most scientists believe that there is no polynomial-time algorithm for this problem in general graphs. However, many efficient algorithms and approximation schemes to resolve the MIS problem are found in some special graph classes. In this thesis, we are going to introduce a separator construction for a diametral path graph. By using a property of the separator, we then obtain a polynomial-time algorithm to find a MIS in diametral path graphs with bounded degree. Additionally, in diametral path graphs, we reduce the approximate MIS problem to finding the solution with the constraint of bounded diameter. This reduction opens a promising approach to an approximate solution for the MIS problem in the future. Adviser: Jitender Deogun