Sagartanu Pal

dblp:287/4341 · DBLP profile ↗
← Back
5ranked-venue papers
0as first author
5since 2021 · last 2025
—ORCID · none

Domains — the database's venue-derived domains; a paper can count in several

Theory of computation · 5 · 5 since 2021Databases, data management, data science and information retrieval · 1 · 1 since 2021
YearPublicationVenuePosition
2025 Algorithms for subgraph complementation to some classes of graphs
Dhanyamol Antony, Sagartanu Pal, R. B. Sandeep
Inf. Process. Lett.2
2024 Switching Classes: Characterization and Computation
abstract
In a graph, the switching operation reverses adjacencies between a subset of vertices and the others. For a hereditary graph class $\mathcal{G}$, we are concerned with the maximum subclass and the minimum superclass of $\mathcal{G}$ that are closed under switching. We characterize the maximum subclass for many important classes $\mathcal{G}$, and prove that it is finite when $\mathcal{G}$ is minor-closed and omits at least one graph. For several graph classes, we develop polynomial-time algorithms to recognize the minimum superclass. We also show that the recognition of the superclass is NP-complete for $H$-free graphs when $H$ is a sufficiently long path or cycle, and it cannot be solved in subexponential time assuming the Exponential Time Hypothesis.
Dhanyamol Antony, Yixin Cao 0001, Sagartanu Pal, R. B. Sandeep
MFCS3
2022 Cutting a Tree with Subgraph Complementation is Hard, Except for Some Small Trees
Dhanyamol Antony, Sagartanu Pal, R. B. Sandeep, R. Subashini
LATIN2
2022 On Subgraph Complementation to H-free Graphs
Dhanyamol Antony, Jay Garchar, Sagartanu Pal, R. B. Sandeep, Sagnik Sen 0001, R. Subashini
Algorithmica3
2021 On Subgraph Complementation to H-free Graphs
Dhanyamol Antony, Jay Garchar, Sagartanu Pal, R. B. Sandeep, Sagnik Sen 0001, R. Subashini
WG3