...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete optimization >An exact approach for the Vertex Coloring Problem
【24h】

An exact approach for the Vertex Coloring Problem

机译：解决顶点着色问题的精确方法

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

摘要

Given an undirected graph G=(V,E), the Vertex Coloring Problem (VCP) requires to assign a color to each vertex in such a way that colors on adjacent vertices are different and the number of colors used is minimized. In this paper, we present an exact algorithm for the solution of VCP based on the well-known Set Covering formulation of the problem. We propose a Branch-and-Price algorithm embedding an effective heuristic from the literature and some methods for the solution of the slave problem, as well as two alternative branching schemes. Computational experiments on instances from the literature show the effectiveness of the algorithm, which is able to solve, for the first time to proven optimality, five of the benchmark instances in the literature, and reduce the optimality gap of many others.
机译：给定无向图G =（V，E），顶点着色问题（VCP）要求为每个顶点分配一种颜色，以使相邻顶点上的颜色不同并且所用颜色的数量最少。在本文中，我们基于问题的众所周知的Set Covering公式，提出了一种精确的VCP解决算法。我们提出了一种Branch-and-Price算法，该算法嵌入了文献中的有效启发式方法和用于解决从属问题的一些方法，以及两种可选的分支方案。文献中实例的计算实验证明了该算法的有效性，该算法首次可以解决已证明的最优性，这是文献中的五个基准实例，并减少了许多其他实例的最优性差距。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号