Friday, September 24 2021
14:00 - 16:00

Alladi Ramakrishnan Hall


Jayakrishnan M.


This thesis consists of parameterized complexity analysis of two classes of problems: (i) graph partitioning problems and (ii) crossing minimisation problems. The first of these, graph partitioning problems, involve testing whether it is possible to partition the vertex set of a graph subject to a set of constraints, or testing whether it is possible to modify a graph slightly by way of vertex deletions, edge deletions etc. so that the vertex set of the resulting graph can be partitioned subject to a set of constraints. The second part of the thesis deals with crossing minimisation problems. Here, the goal is to test if a given graph embedded in the plane contains a certain subgraph with at most a given number of pairwise edge crossings. The thesis contains several new results in these two directions in the realm of Parameterized Complexity.

Topic: Thesis Defense
Time: Sep 24, 2021 02:00 PM India

Join Zoom Meeting

Meeting ID: 945 4272 3307
Passcode: 543634

Download as iCalendar