Two lagrangian relaxation based heuristics for vertex coloring problem

Ali İrfan Mahmutoğulları

doi:10.17776/csj.628518

EN

Two lagrangian relaxation based heuristics for vertex coloring problem

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).

Details

Primary Language

English

Subjects

-

Journal Section

Research Article

Authors

Ali İrfan Mahmutoğulları ^*
0000-0002-8770-8567
Türkiye

Publication Date

June 25, 2020

Submission Date

October 2, 2019

Acceptance Date

June 15, 2020

Published in Issue

Year 2020 Volume: 41 Number: 2

DOI

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

IZ

https://izlik.org/JA25CW39MC

Cite

RIS / Bibtex

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

Öz

Two lagrangian relaxation based heuristics for vertex coloring problem

Abstract

Keywords

References

Details

Primary Language

Subjects

Journal Section

Authors

Publication Date

Submission Date

Acceptance Date

Published in Issue

DOI

IZ

Cite