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

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

Heuristic Algorithms Research of Black White Coloring Problem

Given a graph G and positive integers B and W, the BWC problem asks about the existence of a coloring of G, with B black and W white vertices, such that there is no edge between a black and a white vertex. The optimization version of BWC problem is that we are given a graph G and a positive integer B, and have to color B of the vertices black, so that there will remain as many vertices as possible which are non-adjacent to any of the former B vertices. These latter vertices are to be colored white, and the resulting coloring is optimal. The BWC problem is proved to be NP-complete. We suggest a heuristic algorithms based on tabu List and local search mechanism named BTLSBWC, which yields quite good results for this problem. We compare the result of our algorithm to that of several other known heuristics and obtain the best results in recent literature for the checked graphs.