• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete optimization >Relay placement for two-connectivity
【24h】

Relay placement for two-connectivity

机译：继电器放置以实现两个连接

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Motivated by applications to wireless sensor networks, we study the following problem. We are given a set S of wireless sensor nodes, given as a multiset of points in a normed space.Weseek to place a minimum-size (multi)set Q of wireless relay nodes in the normed space such that the unit-disk graph induced by Q ∪S is two-connected. The unit-disk graph of a set of points has an edge between two points if their distance is at most 1. In Infocom 2006, Kashyap, Khuller, and Shayman present two algorithms, for the two variants of the problem: two-edge-connectivity and biconnectivity. For both they prove an approximation ratio of 2d_(MST), where dMST is the maximum degree of a minimum-degree Minimum Spanning Tree in the normed space. It is known that in the Euclidean twodimensional space, d_(MST) = 5, and in the three dimensional space, d_(MST) = 12. We give a tight analysis of variants of the same algorithms, obtaining approximation ratios of dMST for biconnectivity and 2d_(MST) ? 1 for two-edge-connectivity respectively. To do so we prove additional structural properties regarding bypassing Steiner nodes in biconnected graphs.
机译：受无线传感器网络应用的推动，我们研究了以下问题。我们给定无线传感器节点的集合S，它是在规范空间中以点的多集形式给出的。我们寻求在规范空间中放置无线中继节点的最小大小（多）集Q，从而得出单位磁盘图由Q∪S进行二次连接。如果点的距离最大为1，则一组点的单位磁盘图在两个点之间具有边。在Infocom 2006中，Kashyap，Khuller和Shayman针对该问题的两个变体提出了两种算法：two-edge-连接性和双连接性。对于两者，它们证明了近似比率2d_（MST），其中dMST是范数空间中最小度最小生成树的最大度。已知在欧几里得二维空间中d_（MST）= 5，在三维空间中d_（MST）=12。我们对相同算法的变体进行了严格分析，获得了dMST的双连通性近似比率。和2d_（MST）？ 1分别表示两边连接。为此，我们证明了有关绕过双向图中Steiner节点的其他结构特性。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号