-
Rahul Muthu
(The Institute of Mathematical Sciences, 2009)
An acyclic edge colouring of a graph is an assignment of colours to its edges in such a way that incident edges get distinct colours, and the edges of any cycle use atleast three distinct colours. The latter condition is ...
-
Narayanan, N.
(The Institute of Mathematical Sciences, 2010)
Three graph colouring problems are studied in this thesis with the main focus on 'acyclic edge colouring problem'. The first part of this thesis deals with some classes of graphs and improved upper bounds are obtained. ...
-
Roohani Sharma
(The Institute of Mathematical Sciences, 2020)
With this thesis we advance the algorithmic tool-kit, and contribute to the existing literature concerning parameterized (di)graph cut problems. The study has been conducted from three broad perspectives. The first is the ...
-
Arindam Biswas
(The Institute of Mathematical Sciences, 2022)
This thesis is a study on the existence of algorithms for NP-hard problems in the interval of algorithmic complexity between linear and logarithmic space. In the early days, much research was conducted on the existence of ...
-
Nitin Saurabh
(The Institute of Mathematical Sciences, 2016)
-
Joydeep Mukherjee
(The Institute of Mathematical Sciences, 2019)
-
Diptapriyo Majumdar
(The Institute of Mathematical Sciences, 2018)
In this thesis, we design some classical and lossy kernels for structural parameterizations of some Packing, Covering, and Connectivity problems. Additionally, we provide some hardness results.
Cycle Packing in undirected ...
-
Vijayaraghavan, T. C.
(The Institute of Mathematical Sciences, 2009)
In this thesis the results showing a finer classification of the complexity of several algebraic problems that have efficient polynomial time algorithms are obtained. The problems based on Group theory and Linear Algebra ...
-
Prajakta Nimbhorkar
(The Institute of Mathematical Sciences, 2011)
The focus of this thesis is on the complexity analysis of some computational problems in restricted graph-classes. The problems considered include graph isomorphism, various path problems like reachability, shortest path, ...
-
Yadu Vasudev
(The Institute of Mathematical Sciences, 2014)
-
Jayalal Sarma, M. N.
(The Institute of Mathematical Sciences, 2009)
This thesis studies some combinatorial, topological and linear algebraic parameters associated with Boolean and arithmetic circuits. It is divided into two parts, the first describes a study of combinations of graph ...
-
Kurur, Piyush P.
(2009-09-23)
This thesis studies the Graph Isomorphism and problems that arise in Galois theory. It is targeted to use structural properties of permutation groups together with other algebraic techniques to prove complexity upper ...
-
Soumya Paul
(The Institute of Mathematical Sciences, 2012)
The aim of this work is to study large games: games with a large number
of players and/or with a large temporal, spatial or logical structure, using
techniques from automata theory, logic and game theory. It is argued ...
-
Madhusudan, P.
(2009-08-28)
This thesis studies the problem of automated synthesis of controllers and systems against formal specifications. The two central aims are to study these control problems for branching time specifications and to study them ...
-
Amaldev Manuel
(The Institute of Mathematical Sciences, 2012)
This thesis takes shape in the ongoing study of automata and logics for data words - finite words labelled with elements from an infinite alphabet. The notion of data words is a natural way for modelling unboundedness ...
-
Vinodchandran, N.V.
(, 2009-08-19)
The main contribution of this thesis is in proving upper bounds on the counting complexity of some computational problems that arise from group theory. It consists of two parts. The first part concentrates on studying the ...
-
Ramanathan Thinniyam Srinivasan
(The Institute of Mathematical Sciences, 2019)
-
Fahad, P
(The Institute of Mathematical Sciences, 2015)
This thesis studies algorithms mainly in the parameterized complexity framework.
The thesis has three conceptual parts, (i) efficient computation of representative
families, and its application in FPT and exact algorithms, ...
-
Niranka Banerjee
(The Institute of Mathematical Sciences, 2021)
To analyze an algorithm for a graph problem the traditional notion is to assume that a graph is static. However, for most real world applications graphs are constantly modified. These modifications can be in terms of ...
-
Saket Saurabh
(The Institute of Mathematical Sciences, 2009)
The class of NP-hard combinatorial optimization problems, need to be solved exactly for various applications in theory and practice, brings the need for exact algorithms. Parameterized complexity is an exact algorithmic ...