## Localization in Graphs

##### View/Open

##### Date

1998-10-15##### Author

Khuller, Samir

Raghavachari, Balaji

Rosenfeld, Azriel

##### Metadata

Show full item record##### 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
``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 {\em new\/} result is that the metric dimension can be
approximated in polynomial time within a factor of $O(\log n)$; we also
establish some properties of graphs with metric dimension 2.
(Also cross-referenced as UMIACS-TR-94-92)

University of Maryland, College Park, MD 20742-7011 (301)314-1328.

Please send us your comments.