Florent Foucaud

Tight (Double) Exponential Bounds for Identification Problems: Locating-Dominating Set and Test Cover

Abstract. We investigate fine-grained algorithmic aspects for classical identification problems in graphs, namely, Locating-Dominating Set, and in set systems, namely, Test Cover. In the first problem, an input is a graph [Formula: see text] on [Formula: see text] vertices and an...