Tabu search for the BWC problem

Tabu search for the BWC problem

0.00 Avg rating0 Votes
Article ID: iaor20126634
Volume: 54
Issue: 4
Start Page Number: 649
End Page Number: 667
Publication Date: Dec 2012
Journal: Journal of Global Optimization
Authors: , ,
Keywords: graphs, heuristics: tabu search
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.

Reviews

Required fields are marked *. Your email address will not be published.