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