...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete Applied Mathematics >Coloring graphs by iterated local search traversing feasible and infeasible solutions
【24h】

Coloring graphs by iterated local search traversing feasible and infeasible solutions

机译：通过遍历可行和不可行解决方案的迭代局部搜索为图形着色

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

摘要

Graph coloring is one of the hardest combinatorial optimization problems for which a wide variety of algorithms has been proposed over the last 30 years. The problem is as follows: given a graph one has to assign a label to each vertex such that no monochromatic edge appears and the number of different labels used is minimized. In this paper we present a new heuristic for this problem which works with two different functionalities. One is defined by two greedy subroutines, the former being a greedy constructive one and the other a greedy modification one. The other functionality is a perturbation subroutine, which can produce also infeasible colorings, and the ability is then to retrieve feasible solutions. In our experimentation the proper tuning of this optimization scheme produced good results on known graph coloring benchmarks. (C) 2007 Elsevier B.V. All rights reserved.
机译：图形着色是最困难的组合优化问题之一，在过去的30年中已经提出了各种各样的算法。问题如下：给定一个图，必须为每个顶点分配一个标签，这样就不会出现单色边，并且将使用的不同标签的数量减到最少。在本文中，我们针对此问题提出了一种新的启发式方法，可用于两种不同的功能。一个由两个贪婪的子例程定义，前一个是贪婪的构造性子例程，另一个是贪婪的修改子例程。另一个功能是扰动子例程，它还可以产生不可行的着色，然后可以检索可行的解决方案。在我们的实验中，此优化方案的正确调整在已知的图形着色基准上产生了良好的结果。 （C）2007 Elsevier B.V.保留所有权利。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号