BWC着色问题的一种启发式算法研究

摘要：

无向图的BWC着色问题是给定两个正整数b和w,判断是否存在这样的着色方案:对b个顶点着黑色,对w个顶点着白色,其它顶点不着色,着黑色顶点集合与着白色顶点集合之间没有任何边相连.BWC的最优化问题,是找出一种最优化着色方案,使得与所有黑色顶点不相连接的着白色顶点数最大.该问题被证明是NP-完全问题.提出了一种基于禁忌表和局部搜索机制的混合启发式算法(BTLSBWC),通过对部分网络图进行测试,结果达到了现有文献计算出的最好值.

关键词：BWC问题、启发式算法、局部搜索、禁忌表

所属期刊栏目：14

分类号：O157.5;TP3(代数、数论、组合理论)

资助基金：国家自然科学基金青年科学基金项目61309015

在线出版日期：2014-08-14（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：150-154