Research Article
BibTex RIS Cite

Year 2020, , 493 - 505, 25.06.2020

Ali İrfan Mahmutoğulları

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

Abstract

References

  • [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

Year 2020, , 493 - 505, 25.06.2020

Ali İrfan Mahmutoğulları

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

Abstract

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.

Keywords

Vertex coloring problem heuristics optimization

References

  • [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).
There are 19 citations in total.

Details

Primary Language English
Journal Section Engineering Sciences
Authors

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

Publication Date June 25, 2020
Submission Date October 2, 2019
Acceptance Date June 15, 2020
Published in Issue Year 2020

Cite

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