research
∙
03/05/2023
Expansion Lemma – Variations and Applications to Polynomial-Time Preprocessing
In parameterized complexity, it is well-known that a parameterized probl...
share
research
∙
10/31/2022
Dominator Coloring and CD Coloring in Almost Cluster Graphs
In this paper, we study two popular variants of Graph Coloring – Dominat...
research
∙
01/10/2022
Deletion to Scattered Graph Classes II – Improved FPT Algorithms for Deletion to Pairs of Graph Classes
Let Π be a hereditary graph class. The problem of deletion to Π, takes a...
research
∙
10/27/2021
Structural Parameterizations of Budgeted Graph Coloring
We introduce a variant of the graph coloring problem, which we denote as...
research
∙
07/04/2021
Sublinear-Space Approximation Algorithms for Max r-SAT
In the Max r-SAT problem, the input is a CNF formula with n variables wh...
research
∙
05/10/2021
Parameterized Complexity of Deletion to Scattered Graph Classes
Graph-modification problems, where we add/delete a small number of verti...
research
∙
08/22/2020
Structural Parameterizations of Tracking Paths Problem
Given a graph G with source and destination vertices s,t∈ V(G) respectiv...
research
∙
08/10/2020
Approximation in (Poly-) Logarithmic Space
We develop new approximation algorithms for classical graph and set prob...
research
∙
07/12/2020
Recognizing k-Clique Extendible Orderings
A graph is k-clique-extendible if there is an ordering of the vertices s...
research
∙
02/23/2020
Structural Parameterizations with Modulator Oblivion
It is known that problems like Vertex Cover, Feedback Vertex Set and Odd...
research
∙
01/24/2020
Fixed-parameter tractable algorithms for Tracking Shortest Paths
We consider the parameterized complexity of the problem of tracking shor...
research
∙
01/09/2020
Improved Kernels for Tracking Path Problems
Given a graph G, terminal vertices s and t, and an integer k, the Tracki...
research
∙
11/12/2018
Tractability of Konig Edge Deletion Problems
A graph is said to be a Konig graph if the size of its maximum matching ...
research
∙
11/27/2017
Frameworks for Designing In-place Graph Algorithms
Read-only memory model is a classical model of computation to study time...
research
∙
11/21/2017
Revisiting Connected Vertex Cover: FPT Algorithms and Lossy Kernels
The CONNECTED VERTEX COVER problem asks for a vertex cover in a graph th...
research
∙
06/17/2015