Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4951283 | Journal of Computer and System Sciences | 2017 | 27 Pages |
Abstract
The metric dimension of a graph G is the size of a smallest subset LâV(G) such that for any x,yâV(G) with xâ y there is a zâL such that the graph distance between x and z differs from the graph distance between y and z. Even though this notion has been part of the literature for almost 40 years, prior to our work the computational complexity of determining the metric dimension of a graph was still very unclear. In this paper, we show tight complexity boundaries for the Metric Dimension problem. We achieve this by giving two complementary results. First, we show that the Metric Dimension problem on planar graphs of maximum degree 6 is NP-complete. Then, we give a polynomial-time algorithm for determining the metric dimension of outerplanar graphs.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Josep Diaz, Olli Pottonen, Maria Serna, Erik Jan van Leeuwen,