首页> 外文会议>Algorithms and data structures >The MST of Symmetric Disk Graphs (in Arbitrary Metric Spaces) is Light
【24h】

The MST of Symmetric Disk Graphs (in Arbitrary Metric Spaces) is Light

机译:对称磁盘图的MST(在任意度量空间中)很轻

获取原文
获取原文并翻译 | 示例

摘要

Consider an n-point metric space M = (V, δ), and a transmission range assignment r : V → R+~ that maps each point v € V to the disk of radius r(v) around it. The symmetric disk graph (henceforth, SDG) that corresponds to M and r is the undirected graph over V whose edge set includes an edge (u, v) if both r(u) and r(v) are no smaller than 5(u, v). SDGs are often used to model wireless communication networks. Abu-Affash, Aschner, Carmi and Katz (SWAT 2010, [1]) showed that for any n-point 2-dimensional Euclidean space M, the weight of the MST of every connected SDG for M is O(logn) ? w(MST(M)), and that this bound is tight. However, the upper bound proof of [1] relies heavily on basic geometric properties of constant-dimensional Euclidean spaces, and does not extend to Euclidean spaces of super-constant dimension. A natural question that arises is whether this surprising upper bound of [1] can be generalized for wider families of metric spaces, such as high-dimensional Euclidean spaces. In this paper we generalize the upper bound of Abu-Affash et al. [1] for Euclidean spaces of any dimension. Furthermore, our upper bound extends to arbitrary metric spaces and, in particular, it applies to any of the normed spaces ep. Specifically, we demonstrate that for any n-point metric space M, the weight of the MST of every connected SDG for M is O(logn) ? w(MST(M)).
机译:考虑一个n点度量空间M =(V,δ),以及一个传输范围分配r:V→R +〜,它将每个点v€V映射到半径为r(v)的圆盘上。对应于M且r的对称磁盘图(此后为SDG)是V上的无向图,如果r(u)和r(v)均不小于5(u),则其边集包括边(u,v) ,v)。 SDG通常用于对无线通信网络进行建模。 Abu-Affash,Aschner,Carmi和Katz(SWAT 2010,[1])表明,对于任何n点二维欧几里得空间M,每个连接的SDG的MST的MST权重为O(logn)? w(MST(M)),并且这个界限很严格。然而,[1]的上限证明在很大程度上依赖于恒定维欧几里德空间的基本几何特性,并且没有扩展到超恒定维欧几里德空间。一个自然的问题是,是否可以将[1]的这一令人惊讶的上限推广到更宽的度量空间族,例如高维欧几里德空间。在本文中,我们概括了Abu-Affash等人的上限。 [1]适用于任何维数的欧几里德空间。此外,我们的上限扩展到任意度量空间,并且尤其适用于任何范数空间ep。具体来说,我们证明对于任何n点度量空间M,每个连接的SDG的MST的MST权重为O(logn)? w(MST(M))。

著录项

  • 来源
    《Algorithms and data structures》|2011年|p.691-702|共12页
  • 会议地点 New York NY(US);New York NY(US)
  • 作者

    Shay Solomon;

  • 作者单位

    Department of Computer Science, Ben-Gurion University of the Negev, POB 653, Beer-Sheva 84105, Israel;

  • 会议组织
  • 原文格式 PDF
  • 正文语种 eng
  • 中图分类 TP311.13;
  • 关键词

相似文献

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

客服邮箱:kefu@zhangqiaokeyan.com

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

  • 服务号