Geodesic
Metric dimension of ultrametric spaces
Serdica Mathematical Journal, Tome 46 (2020) no. 2, pp. 195-206.

Voir la notice de l'article provenant de la source Bulgarian Digital Mathematics Library

For an arbitrary finite metric space \((X,d)\) a subset \(A\), \(A \subset X\), is called a resolving set if for any two points \(x\) and \(y\) from the space \(X\) there is an element \(a\) from subset \(A\), such that  distances \(d(a,x)\) and \(d(a,y)\) are different. The metric dimension \(md(X)\) of the space \(X\) is the minimum cardinality of a resolving set. It is well known that the problem of finding the metric dimension of a metric space is NP-complete [7]. In this paper, the metric dimension for finite ultrametric spaces is completely characterized. It is proved that for any finite ultrametric space there exists a polynomial-time algorithm for determining the metric dimension of this spaces.
Keywords: metric dimension, ultrametric space, rooted tree, polynomial-time algorithm, 05B25, 05C12, 68R12 
@article{SMJ2_2020_46_2_a7,
     author = {Oliynyk, Bogdana and Ponomarchuk, Bogdan},
     title = {Metric dimension of ultrametric spaces},
     journal = {Serdica Mathematical Journal},
     pages = {195--206},
     publisher = {mathdoc},
     volume = {46},
     number = {2},
     year = {2020},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/SMJ2_2020_46_2_a7/}
}
TY  - JOUR
AU  - Oliynyk, Bogdana
AU  - Ponomarchuk, Bogdan
TI  - Metric dimension of ultrametric spaces
JO  - Serdica Mathematical Journal
PY  - 2020
SP  - 195
EP  - 206
VL  - 46
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SMJ2_2020_46_2_a7/
LA  - en
ID  - SMJ2_2020_46_2_a7
ER  - 
%0 Journal Article
%A Oliynyk, Bogdana
%A Ponomarchuk, Bogdan
%T Metric dimension of ultrametric spaces
%J Serdica Mathematical Journal
%D 2020
%P 195-206
%V 46
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SMJ2_2020_46_2_a7/
%G en
%F SMJ2_2020_46_2_a7
Oliynyk, Bogdana; Ponomarchuk, Bogdan. Metric dimension of ultrametric spaces. Serdica Mathematical Journal, Tome 46 (2020) no. 2, pp. 195-206. http://geodesic.mathdoc.fr/item/SMJ2_2020_46_2_a7/