• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>Algorithms and Computation; Lecture Notes in Computer Science; 4288 >Balanced Cut Approximation in Random Geometric Graphs
【24h】

Balanced Cut Approximation in Random Geometric Graphs

机译：随机几何图中的平衡割逼近

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

摘要

A random geometric graph G(n,r) is obtained by spreading n points uniformly at random in a unit square, and by associating a vertex to each point and an edge to each pair of points at Euclidian distance at most r. Such graphs are extensively used to model wireless ad-hoc networks, and in particular sensor networks. It is well known that, over a critical value of r, the graph is connected with high probability.rnIn this paper we study the robustness of the connectivity of random geometric graphs in the supercritical phase, under deletion of edges. In particular, we show that, for a sufficiently large r, any cut which separates two components of θ(n) vertices each contains Ω(n~2r~3) edges with high probability. We also present a simple algorithm that, again with high probability, computes one such cut of size O(n~2r~3). From these two results we derive a constant expected approximation algorithm for the β-balanced cut problem on random geometric graphs: find an edge cut of minimum size whose two sides contain at least β n vertices each.
机译：随机几何图G（n，r）是通过在单位正方形中均匀地随机分布n个点，以及将一个顶点与每个点和一个边缘与每对点之间的欧几里得距离最大r关联而获得的。这样的图被广泛地用于对无线自组织网络，特别是传感器网络进行建模。众所周知，在r的临界值上，该图具有很高的概率连通性。rn本文研究了在边缘缺失的情况下，超临界阶段中随机几何图的连通性的鲁棒性。特别地，我们表明，对于一个足够大的r，任何将θ（n）顶点的两个分量分开的切口都包含Ω（n〜2r〜3）个边。我们还提出了一种简单的算法，该算法再次很有可能计算出一个这样的大小为O（n〜2r〜3）的剪切。从这两个结果中，我们推导了针对随机几何图形上的β平衡割问题的恒定期望近似算法：找到一个最小尺寸的边割，其两侧至少包含βn个顶点。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号