Showing cs.DSShow all
2 papers · 1 filter
cs.DS2025
Tight (Double) Exponential Bounds for Identification Problems: Locating-Dominating Set and Test Cover
Dipayan Chakraborty, Florent Foucaud, Diptapriyo Majumdar +1
We investigate fine-grained algorithmic aspects of identification problems in graphs and set systems, with a focus on Locating-Dominating Set and Test Cover. We prove the (tight) c…
cs.DS2024
Structural Parameterization of Locating-Dominating Set and Test Cover
Dipayan Chakraborty, Florent Foucaud, Diptapriyo Majumdar +1
We investigate structural parameterizations of two identification problems: LOCATING-DOMINATING SET and TEST COVER. In the first problem, an input is a graph on vertices an…