2021/11/25 by Yannick Schmitz, Schmitz, Yannick, Egon Wanke +1
Computer Science · #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Graph Labeling and Dimension Problems
paper · pdf · doi:10.48550/arxiv.2111.13054
openalex publication_date 2021/11/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let G be a strongly connected directed graph and u,v,w∈ V(G) be three vertices. Then w strongly resolves u to v if there is a shortest u-w-path containing v or a shortest w-v-path containing u. A set R⊆ V(G) of vertices is a strong resolving set for a directed graph G if for every pair of vertices u,v∈ V(G) there is at least one vertex in R that strongly resolves u to v and at least one vertex in R that strongly resolves v to u. The distances of the vertices of G to and from the vertices of a strong resolving set R uniquely define the connectivity structure of the graph. The Strong Metric Dimension of a directed graph G is the size of a smallest strong resolving set for G. The decision problem Strong Metric Dimension is the question whether G has a strong resolving set of size at most r, for a given directed graph G and a given number r. In this paper we study undirected and directed co-graphs and introduce linear time algorithms for Strong Metric Dimension. These algorithms can also compute strong resolving sets for co-graphs in linear time.