Araştırma Makalesi
BibTex RIS Kaynak Göster

Yıl 2020, , 493 - 505, 25.06.2020

Ali İrfan Mahmutoğulları

https://doi.org/10.17776/csj.628518

Öz

Kaynakça

  • [1] Karp R. M., Reducibility among combinatorial problems. Springer (1972).
  • [2] Diestel R., Graph theory (graduate texts in mathematics). Springer (2005).
  • [3] Brown J. R., Chromatic scheduling and the chromatic number problem. Management Science, 19 (4) (1972) 456–463.
  • [4] Brélaz D., New methods to color the vertices of a graph. Communications of the ACM, 220 (4) (1979) 251–256.
  • [5] Sewell E., An improved algorithm for exact graph coloring. DIMACS series in discrete mathematics and theoretical computer science, 26 (1996) 359-373.
  • [6] Mehrotra A. and Trick M. A., A column generation approach for graph coloring. Informs Journal on Computing, 80 (4) (1996) 344–354.
  • [7] Méndez-Diaz I. and Zabala P., A branch-and-cut algorithm for graph coloring. Discrete Applied Mathematics, 1540 (5) (2006) 826-847.
  • [8] Méndez-Diaz I. and Zabala P., A cutting plane algorithm for graph coloring. Discrete Applied Mathematics, 1560 (2) (2008) 159-179.
  • [9] Leighton F. T., A graph coloring algorithm for large scheduling problems. Journal of research of the national bureau of standards, 840 (6) (1979) 489–506.
  • [10] Bollobás B. and Thomason A., Random graphs of small order. North-Holland Mathematics Studies, 118 (1985) 47-97.
  • [11] Culberson J. C. and Luo F., Exploring the k-colorable landscape with iterated greedy. Cliques, coloring, and satisfiability: second DIMACS implementation challenge, 26 (1996) 245–284.
  • [12] Morgenstern C., Distributed coloration neighborhood search. Discrete Mathematics and Theoretical Computer Science, 26 (1996) 335–358.
  • [13] Chiarandini M., Dumitrescu I., and Stützle T., Stochastic local search algorithms for the graph colouring problem. Handbook of approximation algorithms and metaheuristics. Chapman & Hall, CRC (2007).
  • [14] Hertz A. and de Werra D., Using tabu search techniques for graph coloring. Computing, 390 (4) (1987) 345–351.
  • [15] Johnson D. S., Aragon C. R., McGeoch L. A. and Schevon C., Optimization by simulated annealing: An experimental evaluation; part i, graph partitioning. Operations research, 370 (6) (1989) 865–892.
  • [16] Malaguti E. and Toth P., A survey on vertex coloring problems. International Transactions in Operational Research, 170 (1) (2010) 1–34.
  • [17] Mehrotra A., Constrained graph partitioning: decomposition, polyhedral structure and algorithms, (1992).
  • [18] Hansen P., Labbé M. and Schindl D., Set covering and packing formulations of graph coloring: algorithms and first polyhedral results. Discrete Optimization, 60 (2) (2009) 135–147.
  • [19] Wolsey L.A., Integer programming. Wiley (1998).

Two lagrangian relaxation based heuristics for vertex coloring problem

Yıl 2020, , 493 - 505, 25.06.2020

Ali İrfan Mahmutoğulları

https://doi.org/10.17776/csj.628518

Öz

Vertex coloring problem is a well-known NP-Hard problem where the objective is to minimize the number of colors used to color vertices of a graph ensuring that adjacent vertices cannot have same color. In this paper, we first discuss existing mathematical formulations of the problem and then consider two different heuristics, namely HEUR-RA and HEUR-RC, based on Lagrangian relaxation of adjacency and coloring constraints. HEUR-RA does not require solving any optimization problem through execution whereas at each iteration of HEUR-RC another NP-Hard problem, maximal weight stable set problem, is solved. We conduct experiments to observe computational performances of these heuristics. The experiments reveal that although it requires longer running times, HEUR-RC outperforms HEUR-RA since it provides lower optimal gaps as well as upper bound information.

Anahtar Kelimeler

Vertex coloring problem heuristics optimization

Kaynakça

  • [1] Karp R. M., Reducibility among combinatorial problems. Springer (1972).
  • [2] Diestel R., Graph theory (graduate texts in mathematics). Springer (2005).
  • [3] Brown J. R., Chromatic scheduling and the chromatic number problem. Management Science, 19 (4) (1972) 456–463.
  • [4] Brélaz D., New methods to color the vertices of a graph. Communications of the ACM, 220 (4) (1979) 251–256.
  • [5] Sewell E., An improved algorithm for exact graph coloring. DIMACS series in discrete mathematics and theoretical computer science, 26 (1996) 359-373.
  • [6] Mehrotra A. and Trick M. A., A column generation approach for graph coloring. Informs Journal on Computing, 80 (4) (1996) 344–354.
  • [7] Méndez-Diaz I. and Zabala P., A branch-and-cut algorithm for graph coloring. Discrete Applied Mathematics, 1540 (5) (2006) 826-847.
  • [8] Méndez-Diaz I. and Zabala P., A cutting plane algorithm for graph coloring. Discrete Applied Mathematics, 1560 (2) (2008) 159-179.
  • [9] Leighton F. T., A graph coloring algorithm for large scheduling problems. Journal of research of the national bureau of standards, 840 (6) (1979) 489–506.
  • [10] Bollobás B. and Thomason A., Random graphs of small order. North-Holland Mathematics Studies, 118 (1985) 47-97.
  • [11] Culberson J. C. and Luo F., Exploring the k-colorable landscape with iterated greedy. Cliques, coloring, and satisfiability: second DIMACS implementation challenge, 26 (1996) 245–284.
  • [12] Morgenstern C., Distributed coloration neighborhood search. Discrete Mathematics and Theoretical Computer Science, 26 (1996) 335–358.
  • [13] Chiarandini M., Dumitrescu I., and Stützle T., Stochastic local search algorithms for the graph colouring problem. Handbook of approximation algorithms and metaheuristics. Chapman & Hall, CRC (2007).
  • [14] Hertz A. and de Werra D., Using tabu search techniques for graph coloring. Computing, 390 (4) (1987) 345–351.
  • [15] Johnson D. S., Aragon C. R., McGeoch L. A. and Schevon C., Optimization by simulated annealing: An experimental evaluation; part i, graph partitioning. Operations research, 370 (6) (1989) 865–892.
  • [16] Malaguti E. and Toth P., A survey on vertex coloring problems. International Transactions in Operational Research, 170 (1) (2010) 1–34.
  • [17] Mehrotra A., Constrained graph partitioning: decomposition, polyhedral structure and algorithms, (1992).
  • [18] Hansen P., Labbé M. and Schindl D., Set covering and packing formulations of graph coloring: algorithms and first polyhedral results. Discrete Optimization, 60 (2) (2009) 135–147.
  • [19] Wolsey L.A., Integer programming. Wiley (1998).
Toplam 19 adet kaynakça vardır.

Ayrıntılar

Birincil Dil İngilizce
Bölüm Engineering Sciences
Yazarlar

Ali İrfan Mahmutoğulları 0000-0002-8770-8567

Yayımlanma Tarihi 25 Haziran 2020
Gönderilme Tarihi 2 Ekim 2019
Kabul Tarihi 15 Haziran 2020
Yayımlandığı Sayı Yıl 2020

Kaynak Göster

APA Mahmutoğulları, A. İ. (2020). Two lagrangian relaxation based heuristics for vertex coloring problem. Cumhuriyet Science Journal, 41(2), 493-505. https://doi.org/10.17776/csj.628518