2022/12/08 by M. Wagner, Wagner, Marcel, Yannick Schmitz +3
Computer Science · #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Graph Labeling and Dimension Problems
paper · pdf · doi:10.48550/arxiv.2212.04166
openalex publication_date 2022/12/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Two vertices u and v of an undirected graph G are strongly resolved by a vertex w if there is a shortest path between w and u containing v or a shortest path between w and v containing u. A vertex set R is a strong resolving set for G if for each pair of vertices there is a vertex in R that strongly resolves them. The strong metric dimension of G is the size of a minimum strong resolving set for G. We show that a minimum strong resolving set for an undirected graph G can be computed efficiently if and only if a minimum strong resolving set for each biconnected component of G can be computed efficiently.