-
Ashutosh Rai
(The Institute of Mathematical Sciences, 2016)
This thesis investigates some graph modification problems from Parameterized Complexity point of view. A typical graph modification problem, for a fixed graph class Π, asks us to modify the input graph using small number ...
-
Pranabendu Misra
(The Institute of Mathematical Sciences, 2017)
In this thesis we design algorithms for several network design problems in the framework of parameterized complexity and exact algorithms. Along the way, we also give deterministic algorithms for certain problems in matroid ...
-
Lawqueen Kanesh
(The Institute of Mathematical Sciences, 2020)
-
Sudheshna Kolay
(The Institute of Mathematical Sciences, 2016)
In this thesis, we consider problems in graph partitioning and geometric covering in the realm of Parameterized complexity. Several algorithmic paradigms have been developed in order to cope with the hard problems of ...
-
Praveen, M.
(The Institute of Mathematical Sciences, 2011)
Formal methods for the analysis of concurrent systems is an active area of research. Many mathematical models like Petri nets, communicating automata, automata with auxiliary storage like counters and stacks, rewrite systems ...
-
Ramanujan, M.S.
(The Institute of Mathematical Sciences, 2013)
Menger's theorem, which states that the minimum number of vertices whose removal disconnects two vertices s and t in a graph is equal to the maximum number of pairwise vertex disjoint paths from s to t in the graph, is an ...
-
Somnath Sikdar
(The Institute of Mathematical Sciences, 2010)
Parameterized complexity is a newly developed sub-area of computational complexity that allows for a more refined analysis of problems that are considered hard in the classical sense. In contrast to the classical theory ...
-
Nagaraj, S. V.
(2009-08-24)
This thesis presents new results for four problems in the field of Algorithmic and Computational Number Theory. The first gives an improved analysis of algorithms for testing whether a given positive integer n is a perfect ...
-
Anantha Padmanabha, MS
(The Institute of Mathematical Sciences, 2019)
-
Pushkar S. Joglekar
(The Institute of Mathematical Sciences, 2012)
This thesis explores the computation complexity of some algebraic problems
in the commutative and the noncommutative setting. Motivation is to better understand the algorithmic questions in both the settings and to see ...
-
Meenakshi, B.
(, 2009-09-10)
This thesis is concerned with the use of formal methods towards automatic verification of distributed message passing systems with a fixed finite number of agents. Main concentration is on developing logics to reason about ...
-
Sreejith, A.V.
(The Institute of Mathematical Sciences, 2014)
In this thesis, we study logic on words extended with regular quantifiers. Modulo counting quantifiers are one particular example of such quantifiers, which have been well studied in the past. These quantifiers can be ...
-
Sanjukta Roy
(The Institute of Mathematical Sciences, 2020)
-
Das, Bireswar
(The Institute of Mathematical Sciences, 2010)
The complexity of graph isomorphism problem for restricted classes of graphs are studied and the complexity of group theoretic problems related graph isomorphism are investigated. Several problems closely related to the ...
-
Anup Basil Mathew
(The Institute of Mathematical Sciences, 2017)
In this thesis we study the distributed synthesis problem, which asks for an algorithm that synthesizes distributed systems from a given specification. We study this via the equivalent problem of determining the winning ...
-
Gaurav Rattan
(The Institute of Mathematical Sciences, 2016)
-
Prafullkumar Prabhakar Tale
(The Institute of Mathematical Sciences, 2020)
For a family of graphs F , the F -E DITING problem takes as an input a graph G and an
integer k, and the objective is to decide if at most k edit operations on G can result in a
graph that belongs to F . Various graph ...
-
Sankar Deep Chakraborty
(The Institute of Mathematical Sciences, 2018)
Due to the rapid growth of data, algorithms that utilize the space efficiently are increasingly becoming important. This thesis focusses on an emerging area of designing
algorithms for fundamental graph problems using ...
-
Gaurav Sood
(The Institute of Mathematical Sciences, 2023)
In this thesis, we study the proof complexity of two proof systems: (i) Merge
Resolution proof system for Quantified Boolean Formulas (QBFs), and (ii) MaxSAT
Resolution proof system for certifying unsatisfiability
-
Raghavendra Rao, B. V.
(The Institute of Mathematical Sciences, 2010)
This thesis is broadly divided into two parts: i) Study of width bounded arithmetic circuits, and ii) Computational complexity of matroid isomorphism problems. Various arithmetizations of boolean complexity class NC1 is ...