Research Article
BibTex RIS Cite

Year 2020, Volume: 41 Issue: 2, 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, Volume: 41 Issue: 2, 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 2020Volume: 41 Issue: 2

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