Computing Truncated Metric Dimension of Trees
share
Let G=(V,E) be a simple, unweighted, connected graph. Let d(u,v) denote the distance between vertices u,v. A resolving set of G is a subset S of V such that knowing the distance from a vertex v to every vertex in S uniquely identifies v. The metric dimension of G is defined as the size of the smallest resolving set of G. We define the k-truncated resolving set and k-truncated metric dimension of a graph similarly, but with the notion of distance replaced with d_k(u,v) := min(d(u,v),k+1). In this paper, we demonstrate that computing k-truncated dimension of trees is NP-Hard for general k. We then present a polynomial-time algorithm to compute k-truncated dimension of trees when k is a fixed constant.
READ FULL TEXT