...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Performance evaluation review >Degree-Greedy Algorithms on Large Random Graphs
【24h】

Degree-Greedy Algorithms on Large Random Graphs

机译：大随机图的度贪心算法

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

获取外文期刊封面封底 >>

       
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Computing the size of maximum independent sets is an NP-hard problem for fixed graphs. Characterizing and designing efficient algorithms to compute (or approximate) this independence number for random graphs are notoriously difficult and still largely open issues. In this paper, we show that a low complexity degree-greedy exploration is actually asymptotically optimal on a large class of sparse random graphs. Encouraged by this result, we present and study two variants of sequential exploration algorithms: static and dynamic degree-aware explorations. We derive hydrodynamic limits for both of them, which in turn allow us to compute the size of the resulting independent set. Whereas the former is simpler to compute, the latter may be used to arbitrarily approximate the degree-greedy algorithm. Both can be implemented in a distributed manner. The corresponding hydrodynamic limits constitute an efficient method to compute or bound the independence number for a large class of sparse random graphs. As an application, we then show how our method may be used to compute (or approximate) the capacity of a large 802.11-based wireless network.
机译：对于固定图，计算最大独立集的大小是一个NP难题。表征和设计有效的算法以计算（或近似）随机图的此独立性数非常困难，并且仍然存在很大的问题。在本文中，我们表明，在一大类稀疏随机图上，低复杂度贪婪探索实际上是渐近最优的。受此结果的鼓舞，我们介绍并研究了顺序探索算法的两种变体：静态和动态程度感知探索。我们为它们两个推导了流体动力极限，这反过来又使我们能够计算所得独立集合的大小。尽管前者更易于计算，但后者可用于任意近似度贪心算法。两者都可以以分布式方式实现。相应的水动力极限构成了一种有效的方法，可以计算或限制一大类稀疏随机图的独立性。作为应用程序，我们然后说明如何将我们的方法用于计算（或近似）基于802.11的大型无线网络的容量。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号