Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
The (weighted) metric dimension of graphs: hard and easy cases
Epstein L., Levin A., Woeginger G.  Algorithmica 72 (4): 1130-1171, 2015. Type: Article
Date Reviewed: Aug 31 2015

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.

Reviewer:  Lalit Saxena Review #: CR143731 (1511-0981)
Bookmark and Share
Analysis Of Algorithms (I.1.2 ... )
Cryptographic Controls (D.4.6 ... )
Graph Algorithms (G.2.2 ... )
Algorithms (I.1.2 )
Analysis Of Algorithms And Problem Complexity (F.2 )
Would you recommend this review?
Other reviews under "Analysis Of Algorithms": Date
On minimum sum of radii and diameters clustering
Behsaz B., Salavatipour M.  Algorithmica 73(1): 143-165, 2015. Type: Article
Oct 8 2015
The greedy algorithm for shortest superstrings
Kaplan H., Shafrir N.  Information Processing Letters 93(1): 13-17, 2005. Type: Article
Nov 3 2005
KBFS: K-best-first search
Felner A., Kraus S., Korf R.  Annals of Mathematics and Artificial Intelligence 39(1-2): 19-39, 2003. Type: Article
Oct 24 2005

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright © 2000-2020 ThinkLoud, Inc.
Terms of Use
| Privacy Policy