-
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 ...
-
Limaye, Nutan
(The Institute of Mathematical Sciences, 2010)
The Complexity classes contained in LogCFL is explored in this thesis by drawing connections to Language theory. Many depth reduction techniques involved in this process are studied along the way. The two factor-2 ...
-
Yogesh Dahiya
(The Institute of Mathematical Sciences, 2024)
A central goal of computer science is to understand the capabilities and limitations
of various computational devices. To understand various computational devices
we formalize them using mathematical models called "models ...
-
Aravind, N. R.
(The Institute of Mathematical Sciences, 2011)
This thesis deals mainly with two related coloring problems - forbidden subgraph
colorings and oriented colorings. The former deals with proper colorings of vertices or edges of a graph with constraints on the union of ...
-
Suresh, S. P.
(2009-09-09)
One of the central problems in the automatic verification of security protocols is that of verifying whether a given protocol leaks secrets or not. It identifies syntactic subclasses of protocols for which the secrecy ...