...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete Applied Mathematics >A branch-and-cut algorithm for the equitable coloring problem using a formulation by representatives
【24h】

A branch-and-cut algorithm for the equitable coloring problem using a formulation by representatives

机译：使用代表的公式解决均等着色问题的分枝算法

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

摘要

An equitable k-coloring of a graph is defined by a partition of its vertices into k disjoint stable subsets, such that the difference between the cardinalities of any two subsets is at most one. The equitable coloring problem consists of finding the minimum value of k such that a given graph can be equitably k-colored. We present two new integer programming formulations based on representatives for the equitable coloring problem. We propose a primal constructive heuristic, branching strategies, and the first branch-and-cut algorithm in the literature of the equitable coloring problem. The computational experiments were carried out on randomly generated graphs, DIMACS graphs, and other graphs from the literature.
机译：通过将图的顶点划分为k个不相交的稳定子集，可以定义图的相等k色，从而使任意两个子集的基数之间的差异最大为1。合理的着色问题包括找到k的最小值，以使给定的图可以均匀地进行k色着色。我们根据公平着色问题的代表提出两种新的整数编程公式。我们提出了一种基本的构造性启发式，分支策略以及公平着色问题文献中的第一个分支剪切算法。计算实验是在随机生成的图，DIMACS图和文献中的其他图上进行的。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号