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. Algorithmica72 (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
Classification of all the minimal bilinear algorithms for computing the coefficients of the product of two polynomials modulo a polynomial. Part II
Averbuch A., Galil Z., Winograd S. Theoretical Computer Science 86(2): 143-203, 1991. Type: Article
Dec 1 1992
Parallel algorithms for algebraic problems
von zur Gathen J. (ed) SIAM Journal on Computing 13(4): 802-824, 1984. Type: Article
May 1 1985
Computing in transcendental extensions.
Norman A.   (,2000. Type: Proceedings
Feb 1 1985

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 2004™
Terms of Use
| Privacy Policy