• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>電子情報通信学会技術研究報告. コンピュテ-ション. Theoretical Foundations of Computing >A new method to obtain relaxed problems of the maximum clique problem with using chordal supergraphs and chordal subgraphs
【24h】

A new method to obtain relaxed problems of the maximum clique problem with using chordal supergraphs and chordal subgraphs

机译：通过使用弦和弦图和弦和弦图获得最大群问题的松弛问题的新方法

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

摘要

It is known that Lagrangean relaxation is useful to obtain tight upper bounds for some combinatorial optimization problems. However, for the maximum clique problem, utilizing Lagrangean relaxation in a straightforward manner does not give tight upper bounds. In this paper, we present two methods for obtaining good upper bounds for this problem. In order to construct relaxed problems, the first method makes several chordal supergraphs of the given graph, while the second one creates several vertex induced chordal subgraphs. Experimental results show that our methods can compute better upper bounds than the simple Lagrangean relaxation.
机译：众所周知，拉格朗日松弛法对于获得一些组合优化问题的严格上限很有用。但是，对于最大的集团问题，以直接的方式利用拉格朗日松弛法不会给出严格的上限。在本文中，我们提出了两种方法来获得此问题的良好上限。为了构造松弛问题，第一种方法制作给定图的几个弦超图，而第二种方法则创建几个顶点诱发的弦子图。实验结果表明，与简单的拉格朗日松弛法相比，我们的方法可以计算出更好的上限。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号