On the complexity of metric dimension

Díaz, Josep, Pottonen, Olli, Serna, Maria and van Leeuwen, Erik Jan (2012). On the complexity of metric dimension. In: Leah Epstein and Paolo Ferragina, Algorithms: ESA 2012. 20th Annual European Symposium Proceedings. ESA 2012: 20th Annual European Symposium on Algorithms 2012, Ljubljana, Slovenia, (419-430). 10-12 September, 2012. doi:10.1007/978-3-642-33090-2_37


Author Díaz, Josep
Pottonen, Olli
Serna, Maria
van Leeuwen, Erik Jan
Title of paper On the complexity of metric dimension
Conference name ESA 2012: 20th Annual European Symposium on Algorithms 2012
Conference location Ljubljana, Slovenia
Conference dates 10-12 September, 2012
Proceedings title Algorithms: ESA 2012. 20th Annual European Symposium Proceedings   Check publisher's open access policy
Journal name Lecture Notes in Computer Science   Check publisher's open access policy
Place of Publication Heidelberg, Germany
Publisher Springer
Publication Year 2012
Sub-type Fully published paper
DOI 10.1007/978-3-642-33090-2_37
Open Access Status
ISBN 9783642330896
9783642330902
ISSN 0302-9743
1611-3349
Editor Leah Epstein
Paolo Ferragina
Volume 7501
Start page 419
End page 430
Total pages 12
Language eng
Formatted Abstract/Summary
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) 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, the computational complexity of determining the metric dimension of a graph is still very unclear. Essentially, we only know the problem to be NP-hard for general graphs, to be polynomial-time solvable on trees, and to have a log n-approximation algorithm for general graphs. In this paper, we show tight complexity boundaries for the Mᴇᴛʀɪᴄ Dɪᴍᴇɴsɪᴏɴ problem. We achieve this by giving two complementary results. First, we show that the Mᴇᴛʀɪᴄ Dɪᴍᴇɴsɪᴏɴ problem on bounded-degree planar graphs is NP-complete. Then, we give a polynomial-time algorithm for determining the metric dimension of outerplanar graphs.
Q-Index Code E1
Q-Index Status Provisional Code
Institutional Status Non-UQ

Document type: Conference Paper
Collection: School of Mathematics and Physics
 
Versions
Version Filter Type
Citation counts: Scopus Citation Count Cited 3 times in Scopus Article | Citations
Google Scholar Search Google Scholar
Created: Fri, 12 Sep 2014, 13:37:28 EST by Olli Pottonen on behalf of Mathematics