On optimal approximability results for computing the strong metric dimension
Bhaskar DasGupta
University of Illinois at Chicago
Nasim Mobasheri
University of Illinois at Chicago
PDF
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.