• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>Hybrid Metaheuristics; Lecture Notes in Computer Science; 4030 >Colour Reassignment in Tabu Search for the Graph Set T-Colouring Problem
【24h】

Colour Reassignment in Tabu Search for the Graph Set T-Colouring Problem

机译：在禁忌搜索中重新分配颜色以解决图集T色问题

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

摘要

The graph set T-colouring problem (GSTCP) is a generalisation of the classical graph colouring problem and it is used to model, for example, the assignment of frequencies in mobile networks. The GSTCP asks for the assignment of sets of nonnegative integers to the vertices of a graph so that constraints on the separation of any two numbers assigned to a single vertex or to adjacent vertices are satisfied and some objective function is optimised. Among the various objective functions of interest, we focus on the minimisation of the span, that is, the difference between the largest and the smallest integers used.In practical applications large size instances of the GSTCP are to be solved and heuristic algorithms become necessary. In this article, we propose a new hybrid procedure for the solution of the GSTCP that combines a known tabu search algorithm with an algorithm for the enumeration of all feasible re-assignments of colours to a vertex. We compare the new algorithm with the basic tabu search algorithm and for both we study possible variants. The experimental comparison, supported by statistical analysis, establishes that the new hybrid algorithm performs better on a variety of instance classes.
机译：图集T着色问题（GSTCP）是经典图着色问题的概括，它用于对移动网络中的频率分配进行建模。 GSTCP要求将非负整数集分配给图的顶点，以便满足对分配给单个顶点或相邻顶点的任何两个数字的分隔的约束，并优化某些目标函数。在感兴趣的各种目标函数中，我们着重于最小化跨度，即所使用的最大和最小整数之间的差异。在实际应用中，需要解决GSTCP的大尺寸实例，并且启发式算法变得必要。在本文中，我们为GSTCP的解决方案提出了一种新的混合过程，该过程将已知的禁忌搜索算法与一种将所有可行的颜色重新分配给顶点的算法相结合的算法。我们将新算法与基本禁忌搜索算法进行了比较，并且我们都研究了可能的变体。统计分析支持的实验比较表明，新的混合算法在各种实例类上的性能更好。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号