...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Journal of Combinatorial Optimization >Lower bounds and a tabu search algorithm for the minimum deficiency problem
【24h】

Lower bounds and a tabu search algorithm for the minimum deficiency problem

机译：最小缺陷问题的下界和禁忌搜索算法

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

摘要

An edge coloring of a graph G=(V,E) is a function c:E→? that assigns a color c(e) to each edge e∈E such that c(e)≠c(e′) whenever e and e′ have a common endpoint. Denoting S v (G,c) the set of colors assigned to the edges incident to a vertex v∈V, and D v (G,c) the minimum number of integers which must be added to S v (G,c) to form an interval, the deficiency D(G,c) of an edge coloring c is defined as the sum ∑ v∈V D v (G,c), and the span of c is the number of colors used in c. The problem of finding, for a given graph, an edge coloring with a minimum deficiency is NP-hard. We give new lower bounds on the minimum deficiency of an edge coloring and on the span of edge colorings with minimum deficiency. We also propose a tabu search algorithm to solve the minimum deficiency problem and report experiments on various graph instances, some of them having a known optimal deficiency.
机译：图G =（V，E）的边缘着色是函数c：E→？它将颜色c（e）分配给每个边缘e∈E，以便每当e和e'具有共同端点时c（e）≠c（e'）。表示S v （G，c）分配给入射到顶点v∈V的边的颜色集合，D v （G，c）表示必须加到的最小整数S v （G，c）形成一个间隔，将边缘着色c的缺陷D（G，c）定义为总和∑v∈V D v （G ，c），而c的范围是c中使用的颜色数。对于给定的图形，找到具有最小缺陷的边缘着色的问题是NP-hard。我们为边缘着色的最小缺陷和具有最小缺陷的边缘着色的跨度给出了新的下界。我们还提出了禁忌搜索算法来解决最小缺陷问题，并报告各种图实例的实验，其中一些实例具有已知的最佳缺陷。

著录项

  • 来源
    《Journal of Combinatorial Optimization》 |2009年第2期|168-191|共24页
  • 作者

    Mathieu Bouchard; Alain Hertz; Guy Desaulniers;

  • 作者单位

    Département de Mathématiques et de Génie Industriel école Polytechnique de Montréal and GERAD C.P. 6079 succ. Centre-ville Montréal PQ H3C 3A7 Canada;

    Département de Mathématiques et de Génie Industriel école Polytechnique de Montréal and GERAD C.P. 6079 succ. Centre-ville Montréal PQ H3C 3A7 Canada;

    Département de Mathématiques et de Génie Industriel école Polytechnique de Montréal and GERAD C.P. 6079 succ. Centre-ville Montréal PQ H3C 3A7 Canada;

  • 收录信息
  • 原文格式 PDF
  • 正文语种 eng
  • 中图分类
  • 关键词

    Edge coloring; Minimum deficiency problem; Tabu search;

    机译：边缘着色;最小缺陷问题;Tabu搜索;

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号