Diptapriyo Majumdar

Dr. Diptapriyo Majumdar

orcid

Research Focus & Metrics

Academic Career Length

10Years (2017-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
13 January 2018 in Theory of Computing Systems
Verified
Journal Article
Closed access
PDF file
RKR. Krithika
R. Krithika
DMDiptapriyo Majumdar
Diptapriyo Majumdar
VRVenkatesh Raman
Venkatesh Raman

1 January 2021 in SIAM Journal on Discrete Mathematics
Verified
Journal Article
Closed access
GGGregory Gutin
Gregory Gutin
DMDiptapriyo Majumdar
Diptapriyo Majumdar
SOSebastian Ordyniak
Sebastian Ordyniak
MWMagnus Wahlström
Magnus Wahlström
Golovach, Paulusma, and Song [Inform. and Comput., 237 (2014), pp. 204--214] asked to determine the parameterized complexity of the following problems parameterized by $k$: 1. Given a graph $G$, a ...

26 March 2018 in Theory of Computing Systems
Verified
Journal Article
Closed access
PDF file
DMDiptapriyo Majumdar
Diptapriyo Majumdar
VRVenkatesh Raman
Venkatesh Raman
SSSaket Saurabh
Saket Saurabh

26 February 2018 in Algorithmica
Verified
Journal Article
Closed access
PDF file
DMDiptapriyo Majumdar
Diptapriyo Majumdar
VRVenkatesh Raman
Venkatesh Raman

6 March 2023 in Algorithms
Verified
Journal Article
Open access
PDF file
AJAshwin Jacob
Ashwin Jacob
DMDiptapriyo Majumdar
Diptapriyo Majumdar
VRVenkatesh Raman
Venkatesh Raman
In parameterized complexity, it is well-known that a parameterized problem is fixed-parameter tractable if and only if it has a kernel—an instance equivalent to the input instance, whose size is just a function of the parameter. The size of the kernel can be exponential or worse, resulting in a quest for fixed-parameter tractable problems with polynomial-sized kernels. The developments in machinery (showing lower bounds for the sizes of the kernels) have led researchers to question what are the asymptotically optimum sizes for the kernels of fixed-parameter tractable problems. In this article, we surveyed a tool called expansion lemma that helps in reducing the size of the kernel. Its early origin was in the form of crown decomposition, i.e., to obtain the linear kernel for the Vertex Cover problem; the specific lemma was identified as the tool behind the optimal O(k2) kernel for the undirected feedback vertex set problem. Since then, several variations and extensions of the tool have been discovered. We surveyed them along with their applications in this article.

12 January 2021 in Theory of Computing Systems
Verified
Journal Article
Closed access
PDF file
AJAshwin Jacob
Ashwin Jacob
DMDiptapriyo Majumdar
Diptapriyo Majumdar
VRVenkatesh Raman
Venkatesh Raman