...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Random structures & algorithms >Maximum weight independent sets and matchings in sparse random graphs. Exact results using the local weak convergence method
【24h】

Maximum weight independent sets and matchings in sparse random graphs. Exact results using the local weak convergence method

机译：稀疏随机图中的最大权重独立集和匹配项。使用局部弱收敛方法的精确结果

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

摘要

Let G(n, c) and G(r)(n) be an it-node sparse random graph and a sparse random rregular graph, respectively, and let I(n,r) and I(n, c) be the sizes of the largest independent set in G(n, c) and G(r)(n). The asymptotic value of I(n,c) as it -> infinity, can be computed using the Karp-Sipser algorithm when c <= e. For random cubic graphs, r = 3, it is only known that .432 <= lim inf(n) I(n, 3) <= lim sup(n) I(n, 3) <= .4591 with high probability (w.h.p.) as n -> infinity, as shown in Frieze and Suen [Random Structures Algorithms 5 (1994), 649-664] and Bollabas [European J Combin 1 (1980), 311-316], respectively. In this paper we assume in addition that the nodes of the graph are equipped with nonnegative weights, independently generated according to some common distribution, and we consider instead the maximum weight of an independent set. Surprisingly, we discover that for certain weight distributions, the limit lim, I(n, c) can be computed exactly even when c > e, and lim(n) I(n, r) can be computed exactly for some r >= 1. For example, when the weights are exponentially distributed with parameter 1, lim, I(n, 2e) approximate to .5517, and lim(n) I(n, 3) approximate to .6077. Our results are established using the recently developed local weak convergence method further reduced to a certain local optiniality property exhibited by the models we consider. We extend our results to maximum weight matchings in G(n, c) and G,(n). For the case of exponential distributions, we compute the corresponding limits for every c > 0 and every r >= 2. (c) 2005 Wiley Periodicals, Inc.
机译：令G（n，c / n）和G（r）（n）分别为It-node稀疏随机图和稀疏随机Rregular图，令I（n，r）和I（n，c）为G（n，c / n）和G（r）（n）中最大独立集的大小。当c <= e时，可以使用Karp-Sipser算法计算I（n，c）/ n的渐近值->无穷大。对于随机立方图，r = 3，仅知道.432 <= lim inf（n）I（n，3）/ n <= lim sup（n）I（n，3）/ n <= .4591如Frieze和Suen [Random Structures Algorithms 5（1994），649-664]和Bollabas [European J Combin 1（1980），311-316]所示，它们具有n->无穷大的概率（whp）。在本文中，我们还假定图的节点配备有非负权重，它们是根据某些公共分布独立生成的，而我们考虑的是独立集的最大权重。出乎意料的是，我们发现对于某些权重分布，即使c> e，也可以精确计算极限lim I（n，c）/ n，而对于lim可以精确计算lim（n）I（n，r）/ n一些r> =1。例如，当权重与参数1呈指数分布时，lim，I（n，2e）/ n近似于.5517，而lim（n）I（n，3）/ n近似于。 6077。我们的结果是使用最近开发的局部弱收敛方法建立的，该方法进一步简化为我们考虑的模型所展现的某些局部最优性。我们将结果扩展到G（n，c / n）和G，（n）中的最大权重匹配。对于指数分布，我们为每个c> 0和每个r> = 2计算相应的限制。（c）2005 Wiley Periodicals，Inc.

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号