×

zbMATH — the first resource for mathematics

Tabu search for the BWC problem. (English) Zbl 1263.05027
Summary: 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.

MSC:
05C15 Coloring of graphs and hypergraphs
90C27 Combinatorial optimization
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Alvim A.C.F., Ribeiro C.C., Glover F., Aloise D.J.: A hybrid improvement heuristic for the one-dimensional bin packing problem. J. Heuristics 10, 205–229 (2004) · doi:10.1023/B:HEUR.0000026267.44673.ed
[2] Alabas, C., Altiparmak, F., Dengiz, B.: The optimization of number of kanbans with genetic algorithms, simulated annealing and tabu search. In: Proceedings of the 2000 Congress on Evolutionary Computation CEC00, pp. 580–585. IEEE Press (2000)
[3] Barr B.L., Golden J.P., Kelly J.P., Resende M.G.C., Stewart W.R.: Designing and reporting on computational experiments with heuristic methods. J. Heuristics 1, 9–32 (1995) · Zbl 0853.68154 · doi:10.1007/BF02430363
[4] Berend D., Korach E., Zucker S.: Anticoloring of a family of grid graphs. Discret. Optim. 5/3, 647–662 (2008) · Zbl 1154.05028 · doi:10.1016/j.disopt.2008.02.001
[5] Berend, D., Korach, E., Zucker, S.: Two-anticoloring of planar and related graphs. In: DMTCS Proceedings, AD:335–342. URL: http://www.dmtcs.org/pdfpapers/dmAD0130.pdf (2005) · Zbl 1099.05031
[6] Berend D., Korach E., Zucker S.: A reduction of the anticoloring problem to connected graphs. Electron. Notes Discret. Math. 28, 445–451 (2006) · Zbl 1291.05053 · doi:10.1016/j.endm.2007.01.062
[7] Berend, D., Korach, E., Zucker, S.: Anticoloring and separation of graphs. Discret. Math. (accepted for publication) · Zbl 1215.05055
[8] Berend, D., Zucker, S.: The black-and-white coloring problem on trees. J. Graph Algorithm. Appl. (accepted for publication) · Zbl 1188.05146
[9] Bodirsky, M., Gropl, C., Kang, M.: Generating labeled planar graphs uniformly at random (2007). URL: http://www.informatik.hu-berlin.de/\(\sim\)bodirsky/publications/planar.ps · Zbl 1121.68085
[10] Bray, N.: From mathworld–a wolfram web resource, created by Weisstein, E.W. URL: http://www.mathworld.wolfram.com/GraphStrongProduct.html
[11] Černý V.: A thermodynamical approach to the travelling salesman problem: an efficient simulation algorithm. J. Optim. Theory Appl. 45, 41–51 (1985) · Zbl 0534.90091 · doi:10.1007/BF00940812
[12] Comtet L.: Bonferroni inequalities. Advanced Combinatorics: The Art of Finite and Infinite Expansions, pp. 193–194. Springer, Berlin (1974)
[13] Djidjev H., Venkatesan S.: Reduced constants for simple cycle graph separation. Acta Inform. 34/3, 231–243 (1997) · Zbl 0865.05049 · doi:10.1007/s002360050082
[14] Denise, A., Vasconcellos, M., Welsh, D.J.A.: The random planar graph. Congr. Numerantium 113, 61–79 (1996) URL: http://www.citeseer.ist.psu.edu/denise96random.html · Zbl 0973.05066
[15] Feo T.A., Resende M.G.C.: A probabilistic heuristic for a computationally difficult set covering problem. Oper. Res. Lett. 8, 67–71 (1989) · Zbl 0675.90073 · doi:10.1016/0167-6377(89)90002-3
[16] Glover F.: Future paths for integer programming and links to artificial intelligence. Comput. Oper. Res. 13, 533–549 (1986) · Zbl 0615.90083 · doi:10.1016/0305-0548(86)90048-1
[17] Glover F., McMillan C., Novick B.: Interactive decision software and computer graphics for architectural and space planning. Ann. Oper. Res. 5, 557–573 (1985) · doi:10.1007/BF02023611
[18] Glover F.: Tabu search: part one. ORSA J. Comput. 1, 190–206 (1989) · Zbl 0753.90054 · doi:10.1287/ijoc.1.3.190
[19] Glover F.: Tabu search: part two. ORSA J. Comput. 2, 4–32 (1990) · Zbl 0771.90084 · doi:10.1287/ijoc.2.1.4
[20] Glover F., Laguna M.: Tabu search. Kluwer, Boston, Mass (1997)
[21] Gerke, S., Schlatter, D., Steger, A., Taraz, A.: The Random Planar Graph Process, preprint. URL: http://www-m9.ma.tum.de/\(\sim\)taraz/paper/rpgp.pdf · Zbl 1144.05061
[22] Hansen P., Hertz A., Quinodoz N.: Splitting trees. Discret. Math. 165/6, 403–419 (1997) · Zbl 0873.05036 · doi:10.1016/S0012-365X(96)00187-2
[23] Hart J.P., Shogan A.W.: Semi-greedy heuristics: an empirical study. Oper. Res. Lett. 6, 107–114 (1987) · Zbl 0615.90082 · doi:10.1016/0167-6377(87)90021-6
[24] Hertz A.: Tabu search for large scale timetabling problems. Eur. J. Oper. Res. 54, 39–47 (1991) · Zbl 0729.90660 · doi:10.1016/0377-2217(91)90321-L
[25] Hertz A., Laporte G., Mittaz M.: A tabu search heuristic for the capacitated arc routing problem. Oper. Res. 48(1), 129–135 (2000) · Zbl 1106.90384 · doi:10.1287/opre.48.1.129.12455
[26] Hertz, A., Taillard, E., de Werra, D.: A tutorial on tabu search. In: Proceedings of Giornate di Lavoro AIRO’95 (Entreprise Systems: Management of Technological and Organizational Changes) pp. 13–24 (1995)
[27] Hertz A., de Werra D.: Using tabu search techniques for graph coloring. Computing 39, 345–351 (1987) · Zbl 0626.68051 · doi:10.1007/BF02239976
[28] Johnson, D.S.: A theoretician’s guide to the experimental analysis of algorithms. In: Data Structures, Near Neighbor Searches, and Methodology: Fifth and Sixth DIMACS Implementation Challenges, pp. 215–250. American Mathematical Society (2002)
[29] Kirkpatrick, S., Gelatt, C.D., Vecchi, M.P.: Optimization by simulated annealing. Science 220/4598:671–680 (1983) URL: http://www.citeseer.ist.psu.edu/kirkpatrick83optimization.html · Zbl 1225.90162
[30] Kobler, D., Korach, E., Hertz, A.: On black-and-white colorings, anticolorings and extensions, preprint
[31] Lipton R.J., Tarjan R.E.: A separator theorem for planar graphs. Appl. Math. 36/2, 177–189 (1979) · Zbl 0432.05022
[32] Berkelaar, M.: LPSOLVE package. URL: http://www.lpsolve.sourceforge.net
[33] McKay, B., Brinkmann, G.: A useful planar graph generator (2001). URL: http://cs.anu.edu.au/\(\sim\)bdm/plantri/
[34] Mooney, E.L., Rardin, R.L.: Tabu search for a class of scheduling problems. Ann. Oper. Res. (issue of Tabu Search) (1995) · Zbl 0775.90237
[35] Pitsoulis L.S., Resende M.G.C.: Greedy randomized adaptive search procedure, pp. 178–183. Oxford University Press, Oxford (2002)
[36] Skorin-Kapov J.: Tabu search applied to the quadratic assignment problem. ORSA J. Comput. 1 2, 33–45 (1990) · Zbl 0752.90054 · doi:10.1287/ijoc.2.1.33
[37] Tomlab, Matlab: The tomlab optimization environment. URL: http://www.tomopt.com/tomlab
[38] Weisstein, E.W.: From mathworld–a wolfram web resource. http://www.mathworld.wolfram.com/CartesianProduct.html
[39] Yahalom, O.: Anticoloring problems on graphs. M.Sc. Thesis, Ben-Gurion University (2001)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.