Abstract:
In the real world, we encounter many problems that can be modeled as graphtheoretic
problems. This modeling gives a concrete view of the constraints and
objectives of the problem and allows us to apply some well-known techniques to
solve it. Many of these problems do not have their computational complexity
settled; on the other hand, many others have been proved to be NP-hard. Thus
should be approximated. This thesis focuses on these aspects of some graph
theoretic problems.
The Traveling Tournament Problem is one of the interests of this thesis. A
constrained Traveling Tournament Problem(TTP-k) asks for a schedule of a double
round-robin tournament with an upper bound(k) on the lengths of home stands
and away trips of the teams where the total travel distance is minimized. The
hardness of the problem varies with the upper bound. This thesis attempts an
approximation algorithm for TTP-2, which is assumed to be NP-Hard. Then
considers a study on the hardness analysis of TTP-k where k > 3 and k ∈ N.
The Firefighter Problem is an important graph theoretic problem with practical
application in a recent pandemic scenario. The firefighter problem asks for a
solution to save vertices in a graph by placing firefighters on some of them where
a fire broke out in a vertex and spread through the network with time. This thesis
considers Firefighter Problem on Unit Disk Graphs. Most networks can be modeled
in this wireless era as Unit Disk Graphs. The hardness of the problem and an
approximation algorithm for the same is attempted in this thesis. Then a special
version of the firefighter problem called the Firebreak Problem is considered where
the firefighters can be placed on the vertices only at the initial time instance when
the fire breaks out. An approximation algorithm is attempted for the Firebreak
Problem on Split Graphs which has been proven to be NP-Hard.
