TY - JOUR

T1 - Landmarks in graphs

AU - Khuller, Samir

AU - Raghavachari, Balaji

AU - Rosenfeld, Azriel

N1 - Funding Information:
* Corresponding author. E-mail : samirOcs . umd. edu. ’ Research supported by NSF Research Initiation Award CCR-9307462. * Research supported in part by NSF Research Initiation Award CCR-9409625. 3 Research supported by ARPA under Contract DACA76-92-C-0009 (ARPA Order

PY - 1996/10/8

Y1 - 1996/10/8

N2 - 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 "graph space". The robot can locate itself by the presence of distinctively labeled "landmark" 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's position on the graph? This is actually a classical problem about metric spaces. A minimum set of landmarks which uniquely determine the robot's position is called a "metric basis", and the minimum number of landmarks is called the "metric dimension" 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.

AB - 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 "graph space". The robot can locate itself by the presence of distinctively labeled "landmark" 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's position on the graph? This is actually a classical problem about metric spaces. A minimum set of landmarks which uniquely determine the robot's position is called a "metric basis", and the minimum number of landmarks is called the "metric dimension" 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.

UR - http://www.scopus.com/inward/record.url?scp=0013510156&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0013510156&partnerID=8YFLogxK

U2 - 10.1016/0166-218X(95)00106-2

DO - 10.1016/0166-218X(95)00106-2

M3 - Article

AN - SCOPUS:0013510156

VL - 70

SP - 217

EP - 229

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

SN - 0166-218X

IS - 3

ER -