May, Teresa R.; Oellermann, Ortrud R. The strong dimension of distance-hereditary graphs. (English) Zbl 1233.05097 J. Comb. Math. Comb. Comput. 76, 59-73 (2011). Summary: Let \(G\) be a connected graph. A vertex \(r\) resolves a pair \(u\), \(v\) of vertices of \(G\) if \(u\) and \(v\) are different distances from \(r\). A set \(R\) of vertices of \(G\) is a resolving set for \(G\) if every pair of vertices of \(G\) is resolved by some vertex of \(R\). The smallest cardinality of a resolving set is called the metric dimension of \(G\). A vertex \(r\) strongly resolves a pair \(u\), \(v\) of vertices of \(G\) if there is some shortest \(u-r\) path that contains \(v\) or a shortest \(v-r\) path that contains \(u\). A set \(S\) of vertices of \(G\) is a strong resolving set for \(G\) if every pair of vertices of \(G\) is strongly resolved by some vertex of \(S\); and the smallest cardinality of a strong resolving set of \(G\) is called the strong dimension of \(G\). The problems of finding the metric dimension and strong dimension are NP-hard. Both the metric and strong dimension can be found efficiently for trees. We present efficient solutions for finding the strong dimension of distance-hereditary graphs, a class of graphs that contains the trees. Cited in 16 Documents MSC: 05C12 Distance in graphs 05C85 Graph algorithms (graph-theoretic aspects) Keywords:metric dimension; strong dimension; distance-hereditary graphs PDFBibTeX XMLCite \textit{T. R. May} and \textit{O. R. Oellermann}, J. Comb. Math. Comb. Comput. 76, 59--73 (2011; Zbl 1233.05097)