# Localization in Graphs

 dc.contributor.author Khuller, Samir en_US dc.contributor.author Raghavachari, Balaji en_US dc.contributor.author Rosenfeld, Azriel en_US dc.date.accessioned 2004-05-31T22:27:29Z dc.date.available 2004-05-31T22:27:29Z dc.date.created 1994-07-28 en_US dc.date.issued 1998-10-15 en_US dc.identifier.uri http://hdl.handle.net/1903/655 dc.description.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) en_US dc.format.extent 145401 bytes dc.format.mimetype application/postscript dc.language.iso en_US dc.relation.ispartofseries UM Computer Science Department; CS-TR-3326 en_US dc.relation.ispartofseries UMIACS; UMIACS-TR-94-92 en_US dc.title Localization in Graphs en_US dc.type Technical Report en_US dc.relation.isAvailableAt Digital Repository at the University of Maryland en_US dc.relation.isAvailableAt University of Maryland (College Park, Md.) en_US dc.relation.isAvailableAt Tech Reports in Computer Science and Engineering en_US dc.relation.isAvailableAt UMIACS Technical Reports en_US
﻿