Metric dimension (MD) optimization algorithms require computation in such areas as network verification, mastermind games, metric and digital geometry, image digitization, robot navigation, drug discovery, and combinatorics problems. The authors tend to simplify these polynomial-time algorithms.

This paper generalizes and develops polynomial-time algorithms for MD and weighted MD and for both the weighted and the unweighted problems. The authors describe paths, trees, cycles, co-graphs, k-edge-augmented trees, and wheels using three propositions, 12 lemmas, one theorem, one corollary, and one claim. They extend MD and show that it is NP-complete for the set of graph classes and the input graph for split graphs, bipartite graphs, co-bipartite graphs, and line graphs of bipartite graphs.

The authors emphasize the differences between the weighted and the unweighted cases. For paths and trees, they find a minimum cost endpoint and the cheapest pair of distinct vertices, and a minimum cost set of vertices, at most one vertex per leg, as solutions. The authors find the cheapest pair of non-opposite vertices in the cycle and use the co-tree structure for solving weighted MD for cycles and co-graphs. They also find the cheapest minimal feasible landmark set for computing the weighted MD of a k-edge-augmented tree in polynomial time.

The authors find an optimal solution for weighted MD for wheels in polynomial time using backtracking, which makes this paper an interesting read for those who are working in the area of optimizing MD or weighted MD in polynomial time.