METRIC DIMENSION OF ULTRAMETRIC SPACES.

For an arbitrary finite metric space (X, d) a subset A, A ⊂ 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. [ABSTRACT FROM AUTHOR]