• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete Applied Mathematics >Approximation algorithms for the weighted independent set problem in sparse graphs
【24h】

Approximation algorithms for the weighted independent set problem in sparse graphs

机译：稀疏图中加权独立集问题的近似算法

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

摘要

The approximability of the unweighted independent set problem has been analyzed in terms of sparseness parameters such as the average degree and inductiveness. In the weighted case, no corresponding results are possible for average degree, since adding vertices of small weight can decrease the average degree arbitrarily without significantly changing the approximation ratio. In this paper, we introduce two weighted measures, namely weighted average degree and weighted inductiveness, and analyze algorithms for the weighted independent set problem in terms of these parameters.
机译：根据稀疏性参数（例如平均程度和归纳性）分析了未加权独立集问题的逼近度。在加权情况下，平均度没有相应的结果，因为添加小重量的顶点可以在不显着改变近似比的情况下任意降低平均度。在本文中，我们介绍了加权平均度和加权归纳度两种加权测度，并根据这些参数分析了加权独立集问题的算法。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号