Computer Science – Computational Complexity
Scientific paper
2011-07-12
Computer Science
Computational Complexity
v3: more fitting title, v2: polynomial-time algorithm for outerplanar graphs. Submitted for publication
Scientific paper
The metric dimension of a graph $G$ is the size of a smallest subset $L \subseteq V(G)$ such that for any $x,y \in V(G)$ there is a $z \in 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 Metric Dimension problem. We achieve this by giving two complementary results. First, we show that the Metric Dimension problem on bounded-degree planar graphs is NP-complete. Then, we give a polynomial-time algorithm for determining the metric dimension of outerplanar graphs.
Diaz Josep
Pottonen Olli
Serna Maria
van Leeuwen Erik Jan
No associations
LandOfFree
On the Complexity of Metric Dimension does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with On the Complexity of Metric Dimension, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the Complexity of Metric Dimension will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-565374