Tabu search for the BWC 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. 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. Copyright Springer Science+Business Media, LLC. 2012
Volume (Year): 54 (2012)
Issue (Month): 4 (December)
|Contact details of provider:|| Web page: http://www.springer.com|
|Order Information:||Web: http://www.springer.com/business/operations+research/journal/10898|
References listed on IDEAS
Please report citation or reference errors to , or , if you are the registered author of the cited work, log in to your RePEc Author Service profile, click on "citations" and make appropriate adjustments.:
- Hertz, A., 1991. "Tabu search for large scale timetabling problems," European Journal of Operational Research, Elsevier, vol. 54(1), pages 39-47, September.
When requesting a correction, please mention this item's handle: RePEc:spr:jglopt:v:54:y:2012:i:4:p:649-667. See general information about how to correct material in RePEc.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Sonal Shukla)or (Rebekah McClure)
If references are entirely missing, you can add them using this form.