Loading...
Loading...

Go to the content (press return)

Complexity of metric dimension on planar graphs

Author
Diaz, J.; Pottonen, O.; Serna, M.; van Leeuwen, E.J.
Type of activity
Journal article
Journal
Journal of computer and system sciences
Date of publication
2017-04-03
Volume
83
Number
1
First page
132
Last page
158
DOI
https://doi.org/10.1016/j.jcss.2016.06.006 Open in new window
Repository
http://hdl.handle.net/2117/114459 Open in new window
URL
https://www-sciencedirect-com.recursos.biblioteca.upc.edu/science/article/pii/S0022000016300484 Open in new window
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 Dimen...
Citation
Diaz, J., Pottonen, O., Serna, M., van Leeuwen, E.J. Complexity of metric dimension on planar graphs. "Journal of computer and system sciences", 3 Abril 2017, vol. 83, núm. 1, p. 132-158.
Keywords
Metric dimension, NP-completeness, Outerplanar graph, Planar graph
Group of research
ALBCOM - Algorithms, Computational Biology, Complexity and Formal Methods

Participants

Attachments