Alladi Ramakrishnan Hall

CROSS AND PART: BEYOND THE KNOWN BOUNDARIES

Jayakrishnan M.

IMSc

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
zoom.us/j/94542723307?pwd=bUg5cnVYMEMwUThoZklQbDlSOC9lZz09

Meeting ID: 945 4272 3307
Passcode: 543634