Pawan K. Mishra

dblp:236/0884 · DBLP profile ↗
← Back
4ranked-venue papers
3as first author
2since 2021 · last 2026
0000-0003-3714-7834ORCID · reported

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

Theory of computation · 4 · 3 first-author · 2 since 2021Databases, data management, data science and information retrieval · 1 · 1 first-author · 1 since 2021
YearPublicationVenuePosition
2026 Approximation algorithm for the semitotal domination problem in unit disk graphs
abstract
The Minimum Semitotal Dominating Set (MSTDS) problem is a classical variant of the Minimum Dominating Set (MDS) problem. Given a graph G = ( V , E ) , the goal is to compute a minimum-cardinality vertex subset D ⊆ V such that (i) D is a dominating set, and (ii) for every vertex u in D has a partner v ∈ D within distance two (the semitotal property ), i.e, dist G ( u , v ) ≤ 2 . While the problem is NP-complete in general graphs, recent work has studied approximation algorithms in special graph classes, including unit disk graphs (UDGs). In this paper, we present a deterministic approximation algorithm for the MSTDS problem on UDGs in the graph-based input model, where the graph is provided explicitly without geometric coordinates. Our algorithm achieves a 5.75-approximation factor, improving upon the previous best 6-approximation due to Rout and Das (2024). The core of our algorithm is a multi-stage strategy that starts with a Maximal Independent Set (MIS) and iteratively satisfies the semitotal property through cost-effective vertex swaps and additions of new vertices to the MIS.
Michael A. Henning, Pawan K. Mishra, Kartik Sehgal, Shaurya M. Tripathi, Sridhar Tuli
Discret. Appl. Math.2
2025 Dispersion problem on a convex polygon
Pawan K. Mishra, S. V. Rao 0001, Gautam K. Das
Inf. Process. Lett.1
2020 Capacitated discrete unit disk cover
Pawan K. Mishra, Sangram K. Jena 0001, Gautam K. Das, S. V. Rao 0001
Discret. Appl. Math.1
2019 Capacitated Discrete Unit Disk Cover
Pawan K. Mishra, Sangram K. Jena 0001, Gautam K. Das, S. V. Rao 0001
WALCOM1