Uniquely Localizable Networks with Few Anchors
Uniquely Localizable Networks with Few Anchors
复制标题
具有少量锚点的独特可本地化网络
DOI：
10.1007/11963271_16
复制
发表时间：
2006
期刊：
影响因子：
--
通讯作者：
T. Jordán
中科院分区：
文献类型：
--
作者：
Zsolt Fekete;T. Jordán
在网络定位问题中，一些节点（称为锚）的位置以及一些节点对之间的距离是已知的，目标是确定所有节点的位置。如果存在与给定数据一致的唯一位置集，则称定位问题是可解的（或唯一可定位的）。最近的结果，从图刚性理论使得有可能在两个dimensions.In本文中，我们解决以下相关的优化问题的局部化问题的可解性：给定一组已知的距离在网络中，通过指定一个最小的锚节点的局部化问题可解。我们开发了一个多项式时间的3-近似算法，这个问题证明新的结构图的刚性结果，并通过使用工具从拟阵理论。
In the network localization problem the locations of some nodes (called anchors) as well as the distances between some pairs of nodes are known, and the goal is to determine the location of all nodes. The localization problem is said to be solvable (or uniquely localizable) if there is a unique set of locations consistent with the given data. Recent results from graph rigidity theory made it possible to characterize the solvability of the localization problem in two dimensions.In this paper we address the following related optimization problem: given the set of known distances in the network, make the localization problem solvable by designating a smallest set of anchor nodes. We develop a polynomial-time 3-approximation algorithm for this problem by proving new structural results in graph rigidity and by using tools from matroid theory.