...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete Applied Mathematics >Another look at graph coloring via propositional satisfiability
【24h】

Another look at graph coloring via propositional satisfiability

机译：通过命题可满足性再看图着色

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

摘要

This paper studies the solution of graph coloring problems by encoding into propositional satisfiability problems. The study covers three kinds of satisfiability solvers, based on postorder reasoning (e.g., grasp, chaff), preorder reasoning (e.g., 2cl, 2clsEq), and back-chaining (modoc). The study evaluates three encodings, one of them believed to be new. Some new symmetry-breaking methods, specific to coloring, are used to reduce the redundancy of solutions. A by-product of this research is an implemented lower-bound technique that has shown improved lower bounds for the chromatic numbers of the long-standing unsolved random graphs known as DSJC125.5 and DSJC125.9. Independent-set analysis shows that the chromatic numbers of DSJC125.5 and DSJC125.9 are at least 18 and 40, respectively, but satisfiability encoding was able to demonstrate only that the chromatic numbers are at least 13 and 38, respectively, within available time and space. (C) 2007 Elsevier B.V. All rights reserved.
机译：本文通过编码命题可满足性问题来研究图着色问题的解决方案。该研究涵盖了三种可满足性求解器，它们基于后顺序推理（例如，抓握，草皮），预顺序推理（例如，2cl，2clsEq）和反向链接（modoc）。这项研究评估了三种编码，其中一种被认为是新的。一些特定于着色的新的对称性破缺方法用于减少解决方案的冗余。这项研究的副产品是一种已实现的下界技术，该技术对已知的长期未解决的随机图DSJC125.5和DSJC125.9的色数显示出改进的下界。独立集分析显示，DSJC125.5和DSJC125.9的色数分别至少为18和40，但是可满足性编码仅能够证明在可用时间内色数分别至少为13和38。和空间。 （C）2007 Elsevier B.V.保留所有权利。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号