|
|||||
|
|
Tabu search for the BWC problem |
|
| Authors: | Daniel Berend Ephraim Korach Shira Zucker |
| Affiliation: | 1. Department of Mathematics and Computer Science, Ben-Gurion University, 84105, Beer Sheva, Israel 3. Department of Computer Science, Ben-Gurion University, 84105, Beer Sheva, Israel 2. Department of Industrial Engineering and Management, Ben-Gurion University, 84105, Beer Sheva, Israel 4. Department of software systems, Sapir Academic College, Shaar Hanegev, Israel |
| Abstract: | 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. We suggest a heuristic, based on tabu search, which yields quite good results for this problem. We compare the performance of our algorithm to that of several other known heuristics, and also to what one might expect based on some theoretical results we obtained for the checked graphs. |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ | |