VLDB 2026 Research / reviewers in the wild / expert
Pawan K. Mishra
dblp:236/0884
· DBLP profile ↗
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
| Year | Publication | Venue | Position |
|---|---|---|---|
| 2026 | Approximation algorithm for the semitotal domination problem in unit disk graphsabstractThe 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 |
WALCOM | 1 |