@article {15222,
title = {Landmarks in graphs},
journal = {Discrete Applied Mathematics},
volume = {70},
year = {1996},
month = {1996/10/08/},
pages = {217 - 229},
abstract = {Navigation can be studied in a graph-structured framework in which the navigating agent (which we shall assume to be a point robot) moves from node to node of a {\textquotedblleft}graph space{\textquotedblright}. The robot can locate itself by the presence of distinctively labeled {\textquotedblleft}landmark{\textquotedblright} nodes in the graph space. For a robot navigating in Euclidean space, visual detection of a distinctive landmark provides information about the direction to the landmark, and allows the robot to determine its position by triangulation. On a graph, however, there is neither the concept of direction nor that of visibility. Instead, we shall assume that a robot navigating on a graph can sense the distances to a set of landmarks.Evidently, if the robot knows its distances to a sufficiently large set of landmarks, its position on the graph is uniquely determined. This suggests the following problem: given a graph, what are the fewest number of landmarks needed, and where should they be located, so that the distances to the landmarks uniquely determine the robot{\textquoteright}s position on the graph? This is actually a classical problem about metric spaces. A minimum set of landmarks which uniquely determine the robot{\textquoteright}s position is called a {\textquotedblleft}metric basis{\textquotedblright}, and the minimum number of landmarks is called the {\textquotedblleft}metric dimension{\textquotedblright} of the graph. In this paper we present some results about this problem. Our main new results are that the metric dimension of a graph with n nodes can be approximated in polynomial time within a factor of O(log n), and some properties of graphs with metric dimension two.
},
isbn = {0166-218X},
doi = {10.1016/0166-218X(95)00106-2},
url = {http://www.sciencedirect.com/science/article/pii/0166218X95001062},
author = {Khuller, Samir and Raghavachari,Balaji and Rosenfeld,Azriel}
}