-
PhD (2020) from the Department of Computer Science and Engineering, National Institute of Technology Calicut, Kerala under the supervision of Dr. K Murali Krishnan.
In my Ph. D thesis, we derive a structure theorem that helps to determine whether a plane triangulation (or a plane near-triangulation) is perfect. This leads to a quadratic time algorithm for checking perfectness of plane triangulations (and plane near-triangulations). For the classes of plane triangulations and near-triangulations, the present algorithm is an improvement on the cubic complexity algorithm known earlier, discovered by Hsu (1987) that can test whether an arbitrary planar graph is perfect. The structure theorem states that a plane triangulation (or plane near-triangulation) fails to be perfect if and only if there exists a vertex, an edge or a triangle in the graph, the neighborhood of which has an odd hole as its boundary. Thesis Link.
-
MTech (2011) from the Department of Computer Science and Engineering, National Institute of Technology Calicut, Kerala.
In my M.Tech thesis, the linear-programming dual of the dominating set problem, called the vertex packing problem, is studied. We present a simple proof that shows that the problem does not admit an O(|V|^{1/2−ε}) factor approximation algorithm, for any ε >0, unless NP=ZPP. (Thesis Link)
-
BTech (2005) from the Department of Computer Science and Engineering, Cochin University of Science and Technology, Kerala .