English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Zendy Tools

Zendy Open

The strong metric dimension of a graph was first introduced by Seb\"{o} andTannier (Mathematics of Operations Research, 29(2), 383-393, 2004) as analternative to the (weak) metric dimension of graphs previously introducedindependently by Slater (Proc. 6th Southeastern Conference on Combinatorics,Graph Theory, and Computing, 549-559, 1975) and by Harary and Melter (ArsCombinatoria, 2, 191-195, 1976), and has since been investigated in severalresearch papers. However, the exact worst-case computational complexity ofcomputing the strong metric dimension has remained open beyond beingNP-complete. In this communication, we show that the problem of computing thestrong metric dimension of a graph of $n$ nodes admits a polynomial-time$2$-approximation, admits a $O^\ast\big(2^{\,0.287\,n}\big)$-time exactcomputation algorithm, admits a $O\big(1.2738^k+n\,k\big)$-time exactcomputation algorithm if the strong metric dimension is at most $k$, does notadmit a polynomial time $(2-\varepsilon)$-approximation algorithm assuming theunique games conjecture is true, does not admit a polynomial time$(10\sqrt{5}-21-\varepsilon)$-approximation algorithm assuming P$\neq$NP, doesnot admit a $O^\ast\big(2^{o(n)}\big)$-time exact computation algorithmassuming the exponential time hypothesis is true, and does not admit a$O^\ast\big(n^{o(k)}\big)$-time exact computation algorithm if the strongmetric dimension is at most $k$ assuming the exponential time hypothesis istrue.

On optimal approximability results for computing the strong metric dimension