• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>International Conference on Tools with Artificial Intelligence >Combining MaxSAT Reasoning and Incremental Upper Bound for the Maximum Clique Problem
【24h】

Combining MaxSAT Reasoning and Incremental Upper Bound for the Maximum Clique Problem

机译：将MaxSAT推理和增量上限结合起来以解决最大集团问题

获取原文
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Recently, MaxSAT reasoning has been shown tobe powerful in computing upper bounds for the cardinalityof a maximum clique of a graph. However, existing upperbounds based on MaxSAT reasoning have two drawbacks: (1)at every node of the search tree, MaxSAT reasoning has to beperformed from scratch to compute an upper bound and istime-consuming, (2) due to the NP-hardness of the MaxSATproblem, MaxSAT reasoning generally cannot be complete at anode of a search tree, and may not give an upper bound tightenough for pruning search space. In this paper, we proposean incremental upper bound and combine it with MaxSATreasoning to remedy the two drawbacks. The new approach isused to develop an efficient branch-and-bound algorithm forMaxClique, called IncMaxCLQ. We conduct experiments toshow the complementarity of the incremental upper bound andMaxSAT reasoning and to compare IncMaxCLQ with severalstate-of-the-art algorithms for MaxClique.
机译：最近，已证明MaxSAT推理在计算图的最大派系的基数上限方面功能强大。但是，基于MaxSAT推理的现有上限有两个缺点：（1）在搜索树的每个节点上，必须从头开始执行MaxSAT推理以计算上限，这很耗时;（2）由于NP的难度对于MaxSAT问题，MaxSAT推理通常无法在搜索树的阳极完成，并且可能无法为修剪搜索空间提供上限。在本文中，我们提出了一个增量上限，并将其与MaxSATreasoning相结合以弥补这两个缺点。该新方法用于为MaxClique开发一种有效的分支定界算法，称为IncMaxCLQ。我们进行实验以显示增量上限和MaxSAT推理的互补性，并将IncMaxCLQ与MaxClique的几种最新算法进行比较。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号