Carregant...
Carregant...

Vés al contingut (premeu Retorn)

Complexity of metric dimension on planar graphs

Autor
Diaz, J.; Pottonen, O.; Serna, M.; van Leeuwen, E.J.
Tipus d'activitat
Article en revista
Revista
Journal of computer and system sciences
Data de publicació
2017-04-03
Volum
83
Número
1
Pàgina inicial
132
Pàgina final
158
DOI
https://doi.org/10.1016/j.jcss.2016.06.006 Obrir en finestra nova
Repositori
http://hdl.handle.net/2117/114459 Obrir en finestra nova
URL
https://www-sciencedirect-com.recursos.biblioteca.upc.edu/science/article/pii/S0022000016300484 Obrir en finestra nova
Resum
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...
Citació
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.
Paraules clau
Metric dimension, NP-completeness, Outerplanar graph, Planar graph
Grup de recerca
ALBCOM - Algorismia, Bioinformàtica, Complexitat i Mètodes Formals

Participants

Arxius