On optimal approximability results for computing the strong metric dimension

Minisymposium: METRIC DIMENSION AND RELATED PARAMETERS

Content: We show that the problem of computing the strong metric dimension of a graph can be reduced to the problem of computing a minimum node cover of a transformed graph within an additive logarithmic factor. This implies both a 2-approximation algorithm and a $(2-\varepsilon)$-inapproximability for the problem of computing the strong metric dimension of a graph.

Back to all abstracts