首页> 外文期刊>Theoretical computer science >Large independent sets in general random intersection graphs
【24h】

Large independent sets in general random intersection graphs

机译:一般随机相交图中的大型独立集

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

摘要

We investigate the existence and efficient algorithmic construction of close to optimal independent sets in random models of intersection graphs. In particular, (a) we propose a new model for random intersection graphs (G{sub}(n,m,p)) which includes the model of [M. Karonski, E.R. Scheinerman, K.B. Singer-Cohen, On random intersection graphs: The subgraph problem, Combinatorics, Probability and Computing journal 8 (1999), 131-159] (the "uniform" random intersection graph models) as an important special case. We also define an interesting variation of the model of random intersection graphs, similar in spirit to random regular graphs, (b) For this model we derive exact formulae for the mean and variance of the number of independent sets of size k (for any k) in the graph, (c) We then propose and analyse three algorithms for the efficient construction of large independent sets in this model. The first two are variations of the greedy technique while the third is a totally new algorithm. Our algorithms are analysed for the special case of uniform random intersection graphs. Our analyses show that these algorithms succeed in finding close to optimal independent sets for an interesting range of graph parameters.
机译:我们研究相交图的随机模型中接近最优独立集的存在和有效的算法构造。特别是,(a)我们提出了一个新的随机相交图(G {sub}(n,m,p))模型,其中包括[M. Karonski,E.R. Scheinerman,K.B. Singer-Cohen,关于随机相交图:子图问题,Combinatorics,Probability and Computing journal 8(1999),131-159](“统一”随机相交图模型)是一个重要的特例。我们还定义了一个有趣的随机相交图模型变体,其本质上与随机正则图类似,(b)对于该模型,我们得出大小为k的独立集合数的均值和方差的精确公式(对于任何k )(c)然后,我们提出并分析了三种用于在此模型中有效构建大型独立集的算法。前两个是贪婪技术的变体,而第三个是一种全新的算法。针对均匀随机相交图的特殊情况,分析了我们的算法。我们的分析表明,这些算法成功地找到了有趣的图形参数范围的最佳独立集。

著录项

相似文献

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

客服邮箱:kefu@zhangqiaokeyan.com

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

  • 服务号