...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>SIAM Journal on Discrete Mathematics >FINDING A MAXIMUM INDEPENDENT SET IN A SPARSE RANDOM GRAPH
【24h】

FINDING A MAXIMUM INDEPENDENT SET IN A SPARSE RANDOM GRAPH

机译：在稀疏随机图中找到最大独立集

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

摘要

We consider the problem of finding a maximum independent set in a random graph. The random graph G, which contains n vertices, is modeled as follows. Every edge is included independently with probability d, where d is some sufficiently large constant. Thereafter, for some constant α, a subset I of αn vertices is chosen at random, and all edges within this subset are removed. In this model, the planted independent set I is a good approximation for the maximum independent set I_(max), but both I I_(max) and I_(max) I are likely to be nonempty. We present a polynomial time algorithm that with high probability (over the random choice of random graph G and without being given the planted independent set I) finds the maximum independent set in G when α ≥ (c_o/d)~(1/2), where c_o is some sufficiently large constant independent of d.
机译：我们考虑在随机图中找到最大独立集的问题。包含n个顶点的随机图G的建模如下。每个边缘以概率d / n独立包含，其中d是一些足够大的常数。此后，对于某个常数α，随机选择一个αn个顶点的子集I，并删除该子集中的所有边。在此模型中，种植的独立集I是最大独立集I_（max）的良好近似值，但是I I_（max）和I_（max）I都可能是非空的。我们提出了一种多项式时间算法，当α≥（c_o / d）〜（1/2）时，它有很高的概率（在随机图G的随机选择上，并且没有给出种植的独立集I）在G中找到最大独立集。 ，其中c_o是一些独立于d的足够大的常数。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号