Journal
ALGORITHMICA
Volume 72, Issue 4, Pages 1130-1171Publisher
SPRINGER
DOI: 10.1007/s00453-014-9896-2
Keywords
Graph algorithms; Metric dimension; Graph classes
Ask authors/readers for more resources
Given an input undirected graph , we say that a vertex separates from (where ) if the distance between and differs from the distance from to . A set of vertices is a feasible solution if for every pair of vertices, (), there is a vertex that separates from . Such a feasible solution is called a landmark set, and the metric dimension of a graph is the minimum cardinality of a landmark set. Here, we extend this well-studied problem to the case where each vertex has a non-negative cost, and the goal is to find a feasible solution with a minimum total cost. This weighted version is NP-hard since the unweighted variant is known to be NP-hard. We show polynomial time algorithms for the cases where is a path, a tree, a cycle, a cograph, a -edge-augmented tree (that is, a tree with additional edges) for a constant value of , and a (not necessarily complete) wheel. The results for paths, trees, cycles, and complete wheels extend known polynomial time algorithms for the unweighted version, whereas the other results are the first known polynomial time algorithms for these classes of graphs even for the unweighted version. Next, we extend the set of graph classes for which computing the unweighted metric dimension of a graph is known to be NP-hard. We show that for split graphs, bipartite graphs, co-bipartite graphs, and line graphs of bipartite graphs, the problem of computing the unweighted metric dimension of the graph is NP-hard.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available