{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,27]],"date-time":"2025-08-27T15:43:22Z","timestamp":1756309402310,"version":"3.37.3"},"reference-count":35,"publisher":"EDP Sciences","issue":"3","license":[{"start":{"date-parts":[[2020,3,20]],"date-time":"2020-03-20T00:00:00Z","timestamp":1584662400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.edpsciences.org\/en\/authors\/copyright-and-licensing"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["RAIRO-Oper. Res."],"accepted":{"date-parts":[[2019,3,27]]},"published-print":{"date-parts":[[2020,5]]},"abstract":"<jats:p>The graph coloring problem consists in coloring the vertices of a graph<jats:italic>G=(V, E)<\/jats:italic>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.<\/jats:p>","DOI":"10.1051\/ro\/2019037","type":"journal-article","created":{"date-parts":[[2019,3,29]],"date-time":"2019-03-29T09:03:01Z","timestamp":1553850181000},"page":"845-871","source":"Crossref","is-referenced-by-count":2,"title":["A heuristic for the minimum cost chromatic partition problem"],"prefix":"10.1051","volume":"54","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9478-2351","authenticated-orcid":false,"given":"Celso C.","family":"Ribeiro","sequence":"first","affiliation":[]},{"given":"Philippe L. F.","family":"dos Santos","sequence":"additional","affiliation":[]}],"member":"250","published-online":{"date-parts":[[2020,3,20]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","first-page":"343","DOI":"10.1023\/A:1015061802659","volume":"8","author":"Aiex","year":"2002","journal-title":"J. Heurist."},{"key":"R2","doi-asserted-by":"crossref","first-page":"355","DOI":"10.1007\/s11590-006-0031-4","volume":"1","author":"Aiex","year":"2007","journal-title":"Optim. Lett."},{"key":"R3","doi-asserted-by":"crossref","first-page":"379","DOI":"10.1016\/S0377-2217(02)00832-9","volume":"151","author":"Avanthay","year":"2003","journal-title":"Eur. J. Oper. Res."},{"key":"R4","unstructured":"Bastos M.P. and Ribeiro C.C., Reactive tabu search with path-relinking for the Steiner problem in graphs, In: Essays and Surveys in Metaheuristics edited by Ribeiro C.C. and Hansen P.. Springer, Boston (2002) 39\u201358."},{"key":"R5","doi-asserted-by":"crossref","first-page":"915","DOI":"10.1016\/j.endm.2010.05.116","volume":"36","author":"Bouziri","year":"2010","journal-title":"Electron. Notes Discrete Math."},{"key":"R6","unstructured":"Chiarandini M., Dumitrescu I. and St\u00fctzle T., Stochastic local search algorithms for the graph colouring problem, In: Handbook of Approximation Algorithms and Metaheuristics, edited by Gonzalez T.F. Computer & Information Science Series. Chapman & Hall, Boca Raton (2007) 63.1\u201363.17."},{"key":"R7","doi-asserted-by":"crossref","first-page":"379","DOI":"10.1023\/A:1009823419804","volume":"3","author":"Galinier","year":"1999","journal-title":"J. Comb. Optim."},{"key":"R8","unstructured":"Glover F., Tabu search and adaptive memory programming \u2013 Advances, applications and challenges, In: Interfaces in Computer Science and Operations Research: Advances in Metaheuristics, Optimization, and Stochastic Modeling Technologies, edited by Barr R.S., Helgason R.V. and Kennington J.L., Springer, Boston (1997) 1\u201375."},{"key":"R9","unstructured":"Hamiez J.-P. and Hao J.-K., Scatter search for graph coloring, In: Artificial Evolution, edited by Collet P., Fonlupt C., Hao J.-K., Lutton E. and Schoenauer M.. Vol. 2310 of Lecture Notes in Computer Science. Springer, Berlin (2002) 168\u2013179."},{"key":"R10","unstructured":"Helmar A. and Chiarandini M., A local search heuristic for chromatic sum, In: Proceedings of the 9th Metaheuristics International Conference, Udine, edited by Gaspero L.D., Schaerf A. and St\u00fctzle T. (2011) 161\u2013170."},{"key":"R11","doi-asserted-by":"crossref","first-page":"345","DOI":"10.1007\/BF02239976","volume":"39","author":"Hertz","year":"1987","journal-title":"Computing"},{"key":"R12","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1007\/s10732-006-4192-1","volume":"12","author":"Ho","year":"2006","journal-title":"J. Heurist."},{"key":"R13","unstructured":"Hoos H. and St\u00fctzle T., Evaluation of Las Vegas algorithms \u2013 Pitfalls and remedies, In: Proceedings of the 14th Conference on Uncertainty in Artificial Intelligence, Madison, edited by Cooper G. and Moral S. (1998) 238\u2013245."},{"key":"R14","doi-asserted-by":"crossref","first-page":"1307","DOI":"10.1111\/itor.12419","volume":"24","author":"Interian","year":"2017","journal-title":"Int. Trans. Oper. Res."},{"key":"R15","unstructured":"Jansen K., Complexity results for the optimum cost chromatic partition problem. Universit\u00e4t Trier, Mathematik\/Informatik (1996) 96\u201341."},{"key":"R16","unstructured":"Jansen K., The optimum cost chromatic partition problem, In: Algorithms and Complexity, edited by Bongiovanni G., Bovet D. and Di Battista G. Vol. 1203 of Lecture Notes in Computer Science. Springer, Berlin (1997) 25\u201336."},{"key":"R17","doi-asserted-by":"crossref","first-page":"54","DOI":"10.1006\/jagm.1999.1022","volume":"34","author":"Jansen","year":"2000","journal-title":"J. Algorithms"},{"key":"R18","doi-asserted-by":"crossref","first-page":"367","DOI":"10.1007\/s10462-016-9485-7","volume":"47","author":"Jin","year":"2017","journal-title":"Artif. Intell. Rev."},{"key":"R19","unstructured":"Kroon L.G., Sen A., Deng H. and Roy A., The optimal cost chromatic partition problem for trees and interval graphs, In: Graph-Theoretic Concepts in Computer Science, edited by d\u2019Amore F., Franciosa P. and Marchetti-Spaccamela A. Vol. 1197 of Lecture Notes in Computer Science. Springer, Berlin (1997) 279\u2013292."},{"key":"R20","doi-asserted-by":"crossref","unstructured":"Kubicka E. and Schwenk A.J., An introduction to chromatic sums. In Proceedings of the ACM Seventeenth Annual Computer Science Conference. ACM Press (1989) 39\u201345.","DOI":"10.1145\/75427.75430"},{"key":"R21","doi-asserted-by":"crossref","first-page":"4755","DOI":"10.1016\/j.eswa.2015.01.025","volume":"42","author":"Lai","year":"2015","journal-title":"Expert Syst. Appl."},{"key":"R22","doi-asserted-by":"crossref","first-page":"489","DOI":"10.6028\/jres.084.024","volume":"84","author":"Leighton","year":"1979","journal-title":"J. Res. Nat. Bureau Stand."},{"key":"R23","doi-asserted-by":"crossref","first-page":"503","DOI":"10.1007\/s10732-008-9075-1","volume":"15","author":"Malaguti","year":"2009","journal-title":"J. Heurist."},{"key":"R24","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1111\/j.1475-3995.2009.00696.x","volume":"17","author":"Malaguti","year":"2010","journal-title":"Int. Trans. Oper. Res."},{"key":"R25","unstructured":"Mead C. and Conway L., Introduction to VLSI Systems, Addison-Wesley, Boston (1980)."},{"key":"R26","doi-asserted-by":"crossref","first-page":"104","DOI":"10.1002\/net.10065","volume":"41","author":"Resende","year":"2003","journal-title":"Networks"},{"key":"R27","unstructured":"Resende M.G.C. and Ribeiro C.C., Greedy randomized adaptive search procedures: Advances and applications, In: Handbook of metaheuristics, edited by Gendreau M. and Potvin J.-Y., 2nd edition. Springer, New York (2010) 293\u2013319."},{"key":"R28","doi-asserted-by":"crossref","first-page":"467","DOI":"10.1007\/s11590-011-0322-2","volume":"5","author":"Resende","year":"2011","journal-title":"Optim. Lett."},{"key":"R29","doi-asserted-by":"crossref","unstructured":"Resende M.G.C. and Ribeiro C.C., Optimization by GRASP: Greedy Randomized Adaptive Search Procedures. Springer, Boston (2016).","DOI":"10.1007\/978-1-4939-6530-4"},{"key":"R30","unstructured":"Resende M.G.C., Ribeiro C.C., Glover F. and Mart\u00ed R., Scatter search and path-relinking: Fundamentals, advances, and applications, In: Handbook of metaheuristics, edited by Gendreau M. and Potvin J.-Y., 2nd edition. Springer, New York (2010) 87\u2013107."},{"key":"R31","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1007\/s10732-011-9167-1","volume":"18","author":"Ribeiro","year":"2012","journal-title":"J. Heurist."},{"key":"R32","doi-asserted-by":"crossref","first-page":"641","DOI":"10.1111\/j.1475-3995.2009.00699.x","volume":"16","author":"Ribeiro","year":"2009","journal-title":"Int. Trans. Oper. Res."},{"key":"R33","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1016\/0020-0190(92)90017-P","volume":"43","author":"Sen","year":"1992","journal-title":"Info. Proc. Lett."},{"key":"R34","unstructured":"St\u00fctzle T. and Hoos H.H., Analyzing the run-time behaviour of iterated local search for the tsp. In: III Metaheuristics International Conference, Angra dos Reis (1999) 449\u2013453."},{"key":"R35","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1109\/TCAD.1987.1270250","volume":"6","author":"Supowit","year":"1987","journal-title":"IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst."}],"container-title":["RAIRO - Operations Research"],"original-title":[],"link":[{"URL":"https:\/\/www.rairo-ro.org\/10.1051\/ro\/2019037\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,9,15]],"date-time":"2023-09-15T00:46:55Z","timestamp":1694738815000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.rairo-ro.org\/10.1051\/ro\/2019037"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,3,20]]},"references-count":35,"journal-issue":{"issue":"3"},"alternative-id":["ro190018"],"URL":"https:\/\/doi.org\/10.1051\/ro\/2019037","relation":{},"ISSN":["0399-0559","1290-3868"],"issn-type":[{"type":"print","value":"0399-0559"},{"type":"electronic","value":"1290-3868"}],"subject":[],"published":{"date-parts":[[2020,3,20]]}}}