The graph coloring problem consists in coloring the vertices of a graph G=(V, E) with a minimum number of colors, such as that any two adjacent vertices receive different colors. The minimum cost chromatic partition problem (MCCPP) is an extension of the graph coloring problem in which there are costs associated with the colors and one seeks a vertex coloring minimizing the sum of the costs of the colors used in each vertex. The problem finds applications in VLSI design and in some scheduling problems modeled on interval graphs. We propose a trajectory search heuristic using local search, path-relinking, and perturbations for solving MCCPP and discuss computational results.
Accepté le :
Première publication :
Publié le :
DOI : 10.1051/ro/2019037
Mots-clés : Minimum cost chromatic partition problem, graph coloring problem, metaheuristics, trajectory search heuristic, path-relinking
@article{RO_2020__54_3_845_0,
author = {Ribeiro, Celso C. and dos Santos, Philippe L. F.},
title = {A heuristic for the minimum cost chromatic partition problem},
journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
pages = {845--871},
publisher = {EDP-Sciences},
volume = {54},
number = {3},
year = {2020},
doi = {10.1051/ro/2019037},
mrnumber = {4078189},
zbl = {1443.90302},
language = {en},
url = {http://www.numdam.org/articles/10.1051/ro/2019037/}
}
TY - JOUR AU - Ribeiro, Celso C. AU - dos Santos, Philippe L. F. TI - A heuristic for the minimum cost chromatic partition problem JO - RAIRO - Operations Research - Recherche Opérationnelle PY - 2020 SP - 845 EP - 871 VL - 54 IS - 3 PB - EDP-Sciences UR - http://www.numdam.org/articles/10.1051/ro/2019037/ DO - 10.1051/ro/2019037 LA - en ID - RO_2020__54_3_845_0 ER -
%0 Journal Article %A Ribeiro, Celso C. %A dos Santos, Philippe L. F. %T A heuristic for the minimum cost chromatic partition problem %J RAIRO - Operations Research - Recherche Opérationnelle %D 2020 %P 845-871 %V 54 %N 3 %I EDP-Sciences %U http://www.numdam.org/articles/10.1051/ro/2019037/ %R 10.1051/ro/2019037 %G en %F RO_2020__54_3_845_0
Ribeiro, Celso C.; dos Santos, Philippe L. F. A heuristic for the minimum cost chromatic partition problem. RAIRO - Operations Research - Recherche Opérationnelle, Tome 54 (2020) no. 3, pp. 845-871. doi : 10.1051/ro/2019037. http://www.numdam.org/articles/10.1051/ro/2019037/
[1] , and , Probability distribution of solution time in GRASP: An experimental investigation. J. Heurist. 8 (2002) 343–373. | DOI | Zbl
[2] , and , TTTPLOTS: A Perl program to create time-to-target plots. Optim. Lett. 1 (2007) 355–366. | DOI | MR | Zbl
[3] , and , A variable neighborhood search for graph coloring. Eur. J. Oper. Res. 151 (2003) 379–388. | DOI | MR | Zbl
[4] and , Reactive tabu search with path-relinking for the Steiner problem in graphs, In: Essays and Surveys in Metaheuristics edited by and . Springer, Boston (2002) 39–58. | DOI | MR | Zbl
[5] and , A tabu search approach for the sum coloring problem. Electron. Notes Discrete Math. 36 (2010) 915–922. | DOI | Zbl
[6] , and , Stochastic local search algorithms for the graph colouring problem, In: Handbook of Approximation Algorithms and Metaheuristics, edited by Computer & Information Science Series. Chapman & Hall, Boca Raton (2007) 63.1–63.17.
[7] and , Hybrid evolutionary algorithms for graph coloring. J. Comb. Optim. 3 (1999) 379–397. | DOI | MR | Zbl
[8] , Tabu search and adaptive memory programming – Advances, applications and challenges, In: Interfaces in Computer Science and Operations Research: Advances in Metaheuristics, Optimization, and Stochastic Modeling Technologies, edited by , and , Springer, Boston (1997) 1–75. | Zbl
[9] and , Scatter search for graph coloring, In: Artificial Evolution, edited by , , , and . Vol. 2310 of Lecture Notes in Computer Science. Springer, Berlin (2002) 168–179. | DOI | Zbl
[10] and , A local search heuristic for chromatic sum, In: Proceedings of the 9th Metaheuristics International Conference, Udine, edited by , and (2011) 161–170.
[11] and , Using tabu search techniques for graph coloring. Computing 39 (1987) 345–351. | DOI | MR | Zbl
[12] and , Path relinking for the vehicle routing problem. J. Heurist. 12 (2006) 55–72. | DOI | Zbl
[13] and , Evaluation of Las Vegas algorithms – Pitfalls and remedies, In: Proceedings of the 14th Conference on Uncertainty in Artificial Intelligence, Madison, edited by and (1998) 238–245.
[14] and , A GRASP heuristic using path-relinking and restarts for the Steiner traveling salesman problem. Int. Trans. Oper. Res. 24 (2017) 1307–1323. | DOI | MR | Zbl
[15] , Complexity results for the optimum cost chromatic partition problem. Universität Trier, Mathematik/Informatik (1996) 96–41.
[16] , The optimum cost chromatic partition problem, In: Algorithms and Complexity, edited by , and Vol. 1203 of Lecture Notes in Computer Science. Springer, Berlin (1997) 25–36. | DOI | MR
[17] , Approximation results for the optimum cost chromatic partition problem. J. Algorithms 34 (2000) 54–89. | DOI | MR | Zbl
[18] , and , Algorithms for the minimum sum coloring problem: A review. Artif. Intell. Rev. 47 (2017) 367–394. | DOI
[19] , , and , The optimal cost chromatic partition problem for trees and interval graphs, In: Graph-Theoretic Concepts in Computer Science, edited by , and Vol. 1197 of Lecture Notes in Computer Science. Springer, Berlin (1997) 279–292. | DOI | MR
[20] and , An introduction to chromatic sums. In Proceedings of the ACM Seventeenth Annual Computer Science Conference. ACM Press (1989) 39–45. | DOI
[21] and , Path relinking for the fixed spectrum frequency assignment problem. Expert Syst. Appl. 42 (2015) 4755–4767. | DOI
[22] , A graph coloring algorithm for large scheduling problems. J. Res. Nat. Bureau Stand. 84 (1979) 489–506. | DOI | MR | Zbl
[23] , and , Models and heuristic algorithms for a weighted vertex coloring problem. J. Heurist. 15 (2009) 503–526. | DOI | Zbl
[24] and , A survey on vertex coloring problems. Int. Trans. Oper. Res. 17 (2010) 1–34. | DOI | MR | Zbl
[25] and , Introduction to VLSI Systems, Addison-Wesley, Boston (1980).
[26] and , A GRASP with path-relinking for private virtual circuit routing. Networks 41 (2003) 104–114. | DOI | MR | Zbl
[27] and , Greedy randomized adaptive search procedures: Advances and applications, In: Handbook of metaheuristics, edited by and , 2nd edition. Springer, New York (2010) 293–319.
[28] and , Restart strategies for GRASP with path-relinking heuristics. Optim. Lett. 5 (2011) 467–478. | DOI | MR | Zbl
[29] and , Optimization by GRASP: Greedy Randomized Adaptive Search Procedures. Springer, Boston (2016). | DOI | MR
[30] , , and , Scatter search and path-relinking: Fundamentals, advances, and applications, In: Handbook of metaheuristics, edited by and , 2nd edition. Springer, New York (2010) 87–107. | DOI
[31] and , Path-relinking intensification methods for stochastic local search algorithms. J. Heurist. 18 (2012) 193–214. | DOI
[32] and , A hybrid genetic algorithm for the phylogeny problem using path-relinking as a progressive crossover strategy. Int. Trans. Oper. Res. 16 (2009) 641–657. | DOI
[33] , and , On a graph partition problem with application to VLSI layout. Info. Proc. Lett. 43 (1992) 87–94. | DOI | MR | Zbl
[34] and , Analyzing the run-time behaviour of iterated local search for the tsp. In: III Metaheuristics International Conference, Angra dos Reis (1999) 449–453. | Zbl
[35] , Finding a maximum planar subset of a set of nets in a channel. IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst. 6 (1987) 93–94. | DOI
Cité par Sources :
