{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T13:27:46Z","timestamp":1740144466579,"version":"3.37.3"},"reference-count":29,"publisher":"EDP Sciences","issue":"4","license":[{"start":{"date-parts":[[2023,7,14]],"date-time":"2023-07-14T00:00:00Z","timestamp":1689292800000},"content-version":"vor","delay-in-days":13,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100002322","name":"Coordena\u00e7\u00e3o de Aperfei\u00e7oamento de Pessoal de N\u00edvel Superior","doi-asserted-by":"publisher","award":["001"],"award-info":[{"award-number":["001"]}],"id":[{"id":"10.13039\/501100002322","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003593","name":"Conselho Nacional de Desenvolvimento Cient\u00edfico e Tecnol\u00f3gico","doi-asserted-by":"publisher","award":["422912\/2021-2"],"award-info":[{"award-number":["422912\/2021-2"]}],"id":[{"id":"10.13039\/501100003593","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003593","name":"Conselho Nacional de Desenvolvimento Cient\u00edfico e Tecnol\u00f3gico","doi-asserted-by":"publisher","award":["309315\/ 2019-0"],"award-info":[{"award-number":["309315\/ 2019-0"]}],"id":[{"id":"10.13039\/501100003593","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100005283","name":"Funda\u00e7\u00e3o Cearense de Apoio ao Desenvolvimento Cient\u00edfico e Tecnol\u00f3gico","doi-asserted-by":"publisher","award":["PNE - 0112-00061.01.00"],"award-info":[{"award-number":["PNE - 0112-00061.01.00"]}],"id":[{"id":"10.13039\/501100005283","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100005283","name":"Funda\u00e7\u00e3o Cearense de Apoio ao Desenvolvimento Cient\u00edfico e Tecnol\u00f3gico","doi-asserted-by":"publisher","award":["PS1-0186-00155.01.00\/21"],"award-info":[{"award-number":["PS1-0186-00155.01.00\/21"]}],"id":[{"id":"10.13039\/501100005283","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["RAIRO-Oper. Res."],"accepted":{"date-parts":[[2023,4,28]]},"published-print":{"date-parts":[[2023,7]]},"abstract":"<jats:p>We propose a new integer programming formulation for the Fractional Chromatic Number Problem. The formulation is based on representatives of stable sets. In addition, we present a Lagrangian heuristic from a Lagrangian relaxation of this formulation to obtain a good feasible solution for the problem. Computational experiments are presented to evaluate and compare the upper and lower bounds provided by our approach.<\/jats:p>","DOI":"10.1051\/ro\/2023062","type":"journal-article","created":{"date-parts":[[2023,5,11]],"date-time":"2023-05-11T10:01:24Z","timestamp":1683799284000},"page":"1821-1841","source":"Crossref","is-referenced-by-count":0,"title":["A parallel lagrangian heuristic for the fractional chromatic number of a graph"],"prefix":"10.1051","volume":"57","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9824-3929","authenticated-orcid":false,"given":"Paulo Henrique Mac\u00eado de","family":"Ara\u00fajo","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ricardo C.","family":"Corr\u00eaa","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Manoel","family":"Camp\u00ealo","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"250","published-online":{"date-parts":[[2023,7,14]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","first-page":"397","DOI":"10.1007\/BF01955041","volume":"15","author":"Balas","year":"1996","journal-title":"Algorithmica"},{"key":"R2","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1145\/359094.359101","volume":"22","author":"Br\u00e9laz","year":"1979","journal-title":"Commun. ACM"},{"key":"R3","doi-asserted-by":"crossref","first-page":"503","DOI":"10.1016\/j.endm.2010.05.064","volume":"36","author":"Camp\u00ealo","year":"2010","journal-title":"Elec. Notes Discrete Math."},{"key":"R4","doi-asserted-by":"crossref","first-page":"1097","DOI":"10.1016\/j.dam.2007.05.058","volume":"156","author":"Camp\u00ealo","year":"2008","journal-title":"Discrete Appl. Math."},{"key":"R5","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1590\/S0101-74382009000100009","volume":"29","author":"Camp\u00ealo","year":"2009","journal-title":"Pesqui. Operacional"},{"key":"R6","doi-asserted-by":"crossref","first-page":"730","DOI":"10.1287\/opre.47.5.730","volume":"47","author":"Caprara","year":"1995","journal-title":"Oper. Res."},{"key":"R7","doi-asserted-by":"crossref","first-page":"501","DOI":"10.1145\/88616.88621","volume":"12","author":"Chow","year":"1990","journal-title":"ACM Trans. Program. Lang. Syst."},{"key":"R8","doi-asserted-by":"crossref","first-page":"241","DOI":"10.1016\/0012-365X(76)90036-4","volume":"14","author":"Clarke","year":"1976","journal-title":"Discrete Math."},{"key":"R9","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1016\/0377-2217(85)90167-5","volume":"19","author":"de Werra","year":"1985","journal-title":"Eur. J. Oper. Res."},{"key":"R10","doi-asserted-by":"crossref","first-page":"538","DOI":"10.1137\/18M1214068","volume":"34","author":"Dvo\u0159\u00e1k","year":"2020","journal-title":"SIAM J. Discrete Math."},{"key":"R11","doi-asserted-by":"crossref","first-page":"641","DOI":"10.1112\/jlms\/jdt085","volume":"89","author":"Dvo\u0159\u00e1k","year":"2014","journal-title":"J. London Math. Soc."},{"key":"R12","doi-asserted-by":"crossref","first-page":"8","DOI":"10.1109\/T-VT.1986.24063","volume":"35","author":"Gamst","year":"1986","journal-title":"IEEE Trans. Veh. Technol."},{"unstructured":"Garey M.R. and Johnson D.S., Computers and Intractability; A Guide to the Theory of NP-Completeness. W.H. Freeman & Co., New York, NY, USA (1990).","key":"R13"},{"key":"R14","doi-asserted-by":"crossref","first-page":"1415","DOI":"10.1137\/18M1177317","volume":"33","author":"Gimbel","year":"2019","journal-title":"SIAM J. Discrete Math."},{"key":"R15","doi-asserted-by":"crossref","first-page":"449","DOI":"10.1287\/ijoc.2016.0692","volume":"28","author":"Gleixner","year":"2016","journal-title":"INFORMS J. Comput."},{"unstructured":"Gvozdenovic N., Approximating the stability number and the chromatic number of a graph via semidefinite programming. Ph.D. thesis, Faculty of Science (2008).","key":"R16"},{"key":"R17","first-page":"155","volume":"12","author":"Hell","year":"1982","journal-title":"Ann. Discrete Math."},{"key":"R18","doi-asserted-by":"crossref","first-page":"302","DOI":"10.1112\/blms\/5.3.302","volume":"5","author":"Hilton","year":"1973","journal-title":"Bull. London Math. Soc."},{"unstructured":"Hulst R.v.d., A branch-price-and-cut algorithm for graph coloring. Master\u2019s thesis, University of Twente, The Netherlands (2021).","key":"R19"},{"key":"R20","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1016\/j.tcs.2008.06.048","volume":"406","author":"Klasing","year":"2008","journal-title":"Theor. Comput. Sci."},{"key":"R21","doi-asserted-by":"crossref","first-page":"411","DOI":"10.1002\/jgt.3190190313","volume":"19","author":"Larsen","year":"1995","journal-title":"J. Graph Theory"},{"key":"R22","doi-asserted-by":"crossref","first-page":"586","DOI":"10.1016\/j.orl.2021.06.008","volume":"49","author":"Letchford","year":"2021","journal-title":"Oper. Res. Lett."},{"key":"R23","doi-asserted-by":"crossref","first-page":"960","DOI":"10.1145\/185675.306789","volume":"41","author":"Lund","year":"1994","journal-title":"J. ACM"},{"key":"R24","doi-asserted-by":"crossref","first-page":"344","DOI":"10.1287\/ijoc.8.4.344","volume":"8","author":"Mehrotra","year":"1996","journal-title":"Informs J. Comput."},{"key":"R25","doi-asserted-by":"crossref","first-page":"2815","DOI":"10.1137\/20M1382283","volume":"35","author":"Pirot","year":"2021","journal-title":"SIAM J. Discrete Math."},{"key":"R26","doi-asserted-by":"crossref","first-page":"434","DOI":"10.1007\/s10878-009-9264-3","volume":"21","author":"Rebennack","year":"2011","journal-title":"J. Comb. Optim."},{"unstructured":"Reeves C.R., Modern Heuristic Techniques for Combinatorial Problems. Halsted Press, New York (1993).","key":"R27"},{"key":"R28","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1016\/S0167-6377(00)00060-2","volume":"28","author":"Rossi","year":"2001","journal-title":"Oper. Res. Lett."},{"doi-asserted-by":"crossref","unstructured":"Saad Y., Iterative Methods for Sparse Linear Systems. Second edition. Society for Industrial and Applied Mathematics (2003).","key":"R29","DOI":"10.1137\/1.9780898718003"}],"container-title":["RAIRO - Operations Research"],"original-title":[],"link":[{"URL":"https:\/\/www.rairo-ro.org\/10.1051\/ro\/2023062\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,7,14]],"date-time":"2023-07-14T08:31:49Z","timestamp":1689323509000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.rairo-ro.org\/10.1051\/ro\/2023062"}},"subtitle":[],"editor":[{"given":"M.B.","family":"Campelo Neto","sequence":"first","affiliation":[],"role":[{"role":"editor","vocabulary":"crossref"}]},{"given":"S.","family":"Klein","sequence":"additional","affiliation":[],"role":[{"role":"editor","vocabulary":"crossref"}]},{"given":"I.","family":"Loiseau","sequence":"additional","affiliation":[],"role":[{"role":"editor","vocabulary":"crossref"}]},{"given":"Y.","family":"Wakabayashi","sequence":"additional","affiliation":[],"role":[{"role":"editor","vocabulary":"crossref"}]},{"given":"A.","family":"Weintraub","sequence":"additional","affiliation":[],"role":[{"role":"editor","vocabulary":"crossref"}]},{"given":"V.","family":"dos Santos","sequence":"additional","affiliation":[],"role":[{"role":"editor","vocabulary":"crossref"}]},{"given":"T.","family":"Liebling","sequence":"additional","affiliation":[],"role":[{"role":"editor","vocabulary":"crossref"}]},{"given":"R.","family":"Mahjoub","sequence":"additional","affiliation":[],"role":[{"role":"editor","vocabulary":"crossref"}]},{"given":"N.","family":"Maculan","sequence":"additional","affiliation":[],"role":[{"role":"editor","vocabulary":"crossref"}]}],"short-title":[],"issued":{"date-parts":[[2023,7]]},"references-count":29,"journal-issue":{"issue":"4"},"alternative-id":["ro230158"],"URL":"https:\/\/doi.org\/10.1051\/ro\/2023062","relation":{},"ISSN":["0399-0559","2804-7303"],"issn-type":[{"type":"print","value":"0399-0559"},{"type":"electronic","value":"2804-7303"}],"subject":[],"published":{"date-parts":[[2023,7]]}}}