• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>Federated Conference on Computer Science and Information Systems >Evaluation of metaheuristics for robust graph coloring problem
【24h】

Evaluation of metaheuristics for robust graph coloring problem

机译：鲁棒图着色问题的元启发式评估

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

摘要

In this paper a new formulation of the robust graph coloring problem (RGCP) is proposed. In opposition to classical GCP defined for the given graph G(V,E) not only elements of E but also E can be subject of color conflicts in edge vertices. Conflicts in E are assigned penalties 0<;P(e)<;1. In addition to satisfying constraints related to the number of colors and/or a threshold of the acceptable sum of penalties for color conflicts in graph complementary edges (rigidity level), a new bound called the relative robustness threshold (RRT) is proposed. Then two metaheuristics - SA, TS and their parallel analogues PSA and PTS - for that version of RGCP are presented and experimentally compared. For comparison we use DIMACS graph coloring instances in which a selected percentage of graph edges E is randomly moved to E. Since graph densities and chromatic numbers of DIMACS GCP instances are known in advance, the RGCP instances generated on their basis are more suitable for testing algorithms than totally random instances used so far. The results of the conducted experiments are presented and discussed.
机译：在本文中，提出了鲁棒图着色问题（RGCP）的新公式。与为给定图G（V，E）定义的经典GCP相反，不仅E的元素而且E都可能是边缘顶点中颜色冲突的主题。 E中的冲突被指定为惩罚0 <; P（e）<; 1。除了满足与颜色数量和/或图形互补边中的颜色冲突可接受的惩罚总和的阈值（刚性级别）有关的约束之外，还提出了一个称为相对鲁棒性阈值（RRT）的新界限。然后，针对该版本的RGCP，提出了两种元启发法-SA，TS及其并行类似物PSA和PTS-并进行了实验比较。为了进行比较，我们使用DIMACS图形着色实例，其中选定百分比的图边缘E随机移动到E。由于预先知道了DIMACS GCP实例的图形密度和色数，因此基于它们生成的RGCP实例更适合于测试到目前为止，使用的算法比完全随机的实例要多。介绍并讨论了进行的实验的结果。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号