{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T06:00:14Z","timestamp":1763445614175,"version":"3.37.3"},"reference-count":49,"publisher":"EDP Sciences","issue":"3","license":[{"start":{"date-parts":[[2023,6,26]],"date-time":"2023-06-26T00:00:00Z","timestamp":1687737600000},"content-version":"vor","delay-in-days":56,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100003593","name":"Conselho Nacional de Desenvolvimento Cient\u00edfico e Tecnol\u00f3gico","doi-asserted-by":"publisher","award":["309832\/2020-9"],"award-info":[{"award-number":["309832\/2020-9"]}],"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":["309869\/2020- 0"],"award-info":[{"award-number":["309869\/2020- 0"]}],"id":[{"id":"10.13039\/501100003593","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004586","name":"Funda\u00e7\u00e3o Carlos Chagas Filho de Amparo \u00e0 Pesquisa do Estado do Rio de Janeiro","doi-asserted-by":"publisher","award":["E-26\/210.400\/2018, E-26\/201.344\/2021"],"award-info":[{"award-number":["E-26\/210.400\/2018, E-26\/201.344\/2021"]}],"id":[{"id":"10.13039\/501100004586","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004586","name":"Funda\u00e7\u00e3o Carlos Chagas Filho de Amparo \u00e0 Pesquisa do Estado do Rio de Janeiro","doi-asserted-by":"publisher","award":["E-26\/200.926\/2021"],"award-info":[{"award-number":["E-26\/200.926\/2021"]}],"id":[{"id":"10.13039\/501100004586","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["RAIRO-Oper. Res."],"accepted":{"date-parts":[[2023,5,30]]},"published-print":{"date-parts":[[2023,5]]},"abstract":"<jats:p>A graph is chordal if all its cycles of length greater than or equal to four contain a chord,<jats:italic>i.e.<\/jats:italic>, an edge connecting two nonconsecutive vertices of the cycle. Given a graph<jats:italic>G<\/jats:italic>= (<jats:italic>V<\/jats:italic>,\u00a0<jats:italic>E<\/jats:italic>), the chordal completion problem consists in finding the minimum set of edges to be added to<jats:italic>G<\/jats:italic>to obtain a chordal graph. It has applications in sparse linear systems, database management and computer vision programming. In this article, we developed a biased random-key genetic algorithm (BRKGA) for solving the chordal completion problem, based on the strategy of manipulating permutations that represent perfect elimination orderings of triangulations. Computational results show that the proposed heuristic improve the results of the constructive heuristics fill-in and min-degree. We also developed a strategy for injecting externally constructed feasible solutions coded as random keys into the initial population of the BRKGA that significantly improves the solutions obtained and may benefit other implementations of biased random-key genetic algorithms.<\/jats:p>","DOI":"10.1051\/ro\/2023081","type":"journal-article","created":{"date-parts":[[2023,6,5]],"date-time":"2023-06-05T08:23:58Z","timestamp":1685953438000},"page":"1559-1578","source":"Crossref","is-referenced-by-count":7,"title":["A biased random-key genetic algorithm for the chordal completion problem"],"prefix":"10.1051","volume":"57","author":[{"given":"Samuel E.","family":"Silva","sequence":"first","affiliation":[]},{"given":"Celso C.","family":"Ribeiro","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5320-9209","authenticated-orcid":false,"given":"U\u00e9verton","family":"dos Santos Souza","sequence":"additional","affiliation":[]}],"member":"250","published-online":{"date-parts":[[2023,6,26]]},"reference":[{"key":"R1","unstructured":"Alfaro-Fern\u00e1ndez P., Ruiz R., Pagnozzi F. and St\u00fctzle T., Exploring automatic algorithm design for the hybrid flowshop problem, in 12th Metaheuristics International Conference. Barcelona (2017) 201\u2013203."},{"key":"R2","doi-asserted-by":"crossref","first-page":"154","DOI":"10.1287\/ijoc.6.2.154","volume":"6","author":"Bean","year":"1994","journal-title":"ORSA J. Comput."},{"key":"R3","first-page":"532","volume":"67","author":"Bergman","year":"2019","journal-title":"Oper. Res."},{"key":"R4","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1016\/j.jalgor.2004.07.001","volume":"58","author":"Berry","year":"2006","journal-title":"J. Algor."},{"key":"R5","doi-asserted-by":"crossref","unstructured":"Bodlaender H.L., Kloks T., Kratsch D. and M\u00fcller H., Treewidth and minimum fill-in on d-trapezoid graphs, in Graph Algorithms and Applications I. Edited by Tamassia R. and Tollis I.G.. World Scientific (2002) 139\u2013161.","DOI":"10.1142\/9789812777638_0008"},{"key":"R6","unstructured":"Boisvert R., Pozo R., Remington K., Miller B. and Lipman R., Matrix market, Online reference at http:\/\/math.nist.gov\/MatrixMarket\/ [last access on March 21, 2023] (2007)."},{"key":"R7","doi-asserted-by":"crossref","first-page":"212","DOI":"10.1137\/S0097539799359683","volume":"31","author":"Bouchitt\u00e9","year":"2001","journal-title":"SIAM J. Comput."},{"key":"R8","doi-asserted-by":"crossref","first-page":"823","DOI":"10.1111\/itor.12178","volume":"22","author":"Brand\u00e3o","year":"2015","journal-title":"Int. Trans. Oper. Res."},{"key":"R9","doi-asserted-by":"crossref","first-page":"1061","DOI":"10.1111\/itor.12429","volume":"24","author":"Brand\u00e3o","year":"2017","journal-title":"Int. Trans. Oper. Res."},{"key":"R10","doi-asserted-by":"crossref","first-page":"3137","DOI":"10.1051\/ro\/2022141","volume":"56","author":"Brito","year":"2022","journal-title":"RAIRO: OR"},{"key":"R11","doi-asserted-by":"crossref","unstructured":"Broersma H.J., Dahlhaus E. and Kloks T., Algorithms for the treewidth and minimum fill-in of HHD-free graphs, in Graph-Theoretic Concepts in Computer Science. Vol. 1335 of Lecture Notes in Computer Science. Edited by M\u00f6hring R.H.. Springer (1997) 109\u2013117.","DOI":"10.1007\/BFb0024492"},{"key":"R12","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1016\/0012-365X(74)90002-8","volume":"9","author":"Buneman","year":"1974","journal-title":"Discrete Math."},{"key":"R13","doi-asserted-by":"crossref","first-page":"171","DOI":"10.1016\/0020-0190(96)00050-6","volume":"58","author":"Cai","year":"1996","journal-title":"Inf. Process. Lett."},{"key":"R14","doi-asserted-by":"crossref","unstructured":"Chang M.-S., Algorithms for maximum matching and minimum fill-in on chordal bipartite graphs, in Algorithms and Computation. Volume 1178 of Lecture Notes in Computer Science. Edited by Asano T., Igarashi Y., Nagamochi H., Miyano S. and Suri S.. Springer (1996) 146\u2013155.","DOI":"10.1007\/BFb0009490"},{"key":"R15","doi-asserted-by":"crossref","first-page":"174","DOI":"10.1016\/j.cor.2015.10.009","volume":"67","author":"Chaves","year":"2016","journal-title":"Comput. Oper. Res."},{"key":"R16","doi-asserted-by":"crossref","first-page":"96","DOI":"10.1006\/jctb.1994.1056","volume":"62","author":"Chung","year":"1994","journal-title":"J. Comb. Theory Ser. B"},{"key":"R17","unstructured":"Dell H., Komusiewicz C., Talmon N. and Weller M., The PACE 2017 parameterized algorithms and computational experiments challenge: the second iteration, in 12th International Symposium on Parameterized and Exact Computation. Vol. 89 of Leibniz International Proceedings in Informatics. Edited by Lokshtanov D. and Nishimura N.. Dagstuhl (2018) 30:1\u201330:12 (Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik. Online reference at http:\/\/drops.dagstuhl.de\/opus\/volltexte\/2018\/8558 [last access on March 21, 2023])."},{"key":"R18","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1007\/BF02992776","volume":"25","author":"Dirac","year":"1961","journal-title":"Abh. Math. Semin. Univ. Hambg."},{"key":"R19","doi-asserted-by":"crossref","first-page":"1923","DOI":"10.1093\/molbev\/msu132","volume":"31","author":"Douzery","year":"2014","journal-title":"Mol. Biol. Evol."},{"key":"R20","doi-asserted-by":"crossref","first-page":"2197","DOI":"10.1137\/11085390X","volume":"42","author":"Fomin","year":"2013","journal-title":"SIAM J. Comput."},{"key":"R21","doi-asserted-by":"crossref","first-page":"1058","DOI":"10.1137\/050643350","volume":"38","author":"Fomin","year":"2008","journal-title":"SIAM J. Comput."},{"key":"R22","doi-asserted-by":"crossref","first-page":"835","DOI":"10.2140\/pjm.1965.15.835","volume":"15","author":"Fulkerson","year":"1965","journal-title":"Pac. J. Math."},{"key":"R23","unstructured":"Garey M.R. and Johnson D.S., Computers and Intractability: A Guide to the Theory of NP-completeness. W.H. Freeman and Co (1979)."},{"key":"R24","doi-asserted-by":"crossref","first-page":"487","DOI":"10.1007\/s10732-010-9143-1","volume":"17","author":"Gon\u00e7alves","year":"2011","journal-title":"J. Heuristics"},{"key":"R25","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1590\/0101-7438.2014.034.02.0143","volume":"34","author":"Gon\u00e7alves","year":"2014","journal-title":"Pesqui. Operacional"},{"key":"R26","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1016\/0024-3795(84)90207-6","volume":"58","author":"Grone","year":"1984","journal-title":"Linear Algebra Appl."},{"key":"R27","doi-asserted-by":"crossref","unstructured":"Gysel R., Stevens K. and Gusfield D., Reducing problems in unrooted tree compatibility to restricted triangulations of intersection graphs, in Algorithms in Bioinformatics. Vol. 7534 of Lecture Notes in Computer Science. Edited by Raphael B. and Tang J.. Springer (2012) 93\u2013105.","DOI":"10.1007\/978-3-642-33122-0_8"},{"key":"R28","doi-asserted-by":"crossref","first-page":"90","DOI":"10.1137\/1024022","volume":"24","author":"Hartmanis","year":"1982","journal-title":"SIAM Rev."},{"key":"R29","doi-asserted-by":"crossref","first-page":"297","DOI":"10.1016\/j.disc.2005.12.003","volume":"306","author":"Heggernes","year":"2006","journal-title":"Discrete Math."},{"key":"R30","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1007\/s10107-010-0402-6","volume":"129","author":"Kim","year":"2011","journal-title":"Math. Prog."},{"key":"R31","doi-asserted-by":"crossref","first-page":"272","DOI":"10.1006\/jagm.1998.0936","volume":"28","author":"Kloks","year":"1998","journal-title":"J. Algor."},{"key":"R32","unstructured":"Kobayashi Y. and Tamaki H., Track B: Minimum fill-in. Online reference at https:\/\/github.com\/TCS-Meiji\/PACE2017-TrackB, [last access on October 30, 2022] (2017)."},{"key":"R33","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1111\/j.2517-6161.1988.tb01721.x","volume":"50","author":"Lauritzen","year":"1988","journal-title":"J. Royal Stat. Soc. Ser. B"},{"key":"R34","first-page":"43","volume":"3","author":"L\u00f3pez-Ib\u00e1\u00f1ez","year":"2016","journal-title":"Oper. Res. Perspect."},{"key":"R35","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1145\/272991.272995","volume":"8","author":"Matsumoto","year":"1998","journal-title":"ACM Trans. Model. Comput. Simul."},{"key":"R36","doi-asserted-by":"crossref","first-page":"958","DOI":"10.1016\/j.tcs.2009.10.004","volume":"411","author":"Mezzini","year":"2010","journal-title":"Theor. Comput. Sci."},{"key":"R37","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1007\/s10107-002-0351-9","volume":"95","author":"Nakata","year":"2003","journal-title":"Math. Prog."},{"key":"R38","doi-asserted-by":"crossref","first-page":"1067","DOI":"10.1137\/S0097539798336073","volume":"30","author":"Natanzon","year":"2000","journal-title":"SIAM J. Comput."},{"key":"R39","doi-asserted-by":"crossref","unstructured":"P\u00e9rez C\u00e1ceres L., L\u00f3pez-Ib\u00e1\u00f1ez M. and St\u00fctzle T., An analysis of parameters of irace, in Evolutionary Computation in Combinatorial Optimization. Vol. 8600 of Lecture Notes in Computer Science. Edited by Blum C. and Ochoa D.. Springer (2014) 37\u201348.","DOI":"10.1007\/978-3-662-44320-0_4"},{"key":"R40","doi-asserted-by":"crossref","first-page":"849","DOI":"10.1016\/j.ejor.2018.05.071","volume":"271","author":"Pinto","year":"2018","journal-title":"Eur. J. Oper. Res."},{"key":"R41","doi-asserted-by":"crossref","first-page":"S741","DOI":"10.1051\/ro\/2020003","volume":"55","author":"Pinto","year":"2021","journal-title":"RAIRO: OR"},{"key":"R42","doi-asserted-by":"crossref","first-page":"241","DOI":"10.1186\/1471-2148-7-241","volume":"7","author":"Ranwez","year":"2007","journal-title":"BMC Evol. Biol."},{"key":"R43","first-page":"759","volume":"6876","author":"Rollon","year":"2011","journal-title":"Principles and Practice of Constraint Programming"},{"key":"R44","doi-asserted-by":"crossref","unstructured":"Rossi R. and Ahmed N., The network data repository with interactive graph analytics and visualization, in Twenty-Ninth AAAI conference on Artificial Intelligence (2015) 22\u201335.","DOI":"10.1609\/aaai.v29i1.9277"},{"key":"R45","unstructured":"Silva S.E., Test instances for the chordal completion problem. Mendeley Data, V1. Online publication at https:\/\/data.mendeley.com\/datasets\/mf33kd592n [last access on March 21, 2023] (2022)."},{"key":"R46","unstructured":"Spears W. and De Jong K.A.. On the virtues of parameterized uniform crossover, in Proceedings of the Fourth International Conference on Genetic Algorithms. Edited by Belew R. and Booker L.. San Mateo (1991) 230\u2013236."},{"key":"R47","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1080\/10556788.2014.890197","volume":"30","author":"Toso","year":"2015","journal-title":"Optimiz. Methods Soft."},{"key":"R48","doi-asserted-by":"crossref","first-page":"241","DOI":"10.1561\/2400000006","volume":"1","author":"Vandenberghe","year":"2015","journal-title":"Found. Trends Optimiz."},{"key":"R49","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1137\/0602010","volume":"2","author":"Yannakakis","year":"1981","journal-title":"SIAM J. Algebraic Discrete Methods"}],"container-title":["RAIRO - Operations Research"],"original-title":[],"link":[{"URL":"https:\/\/www.rairo-ro.org\/10.1051\/ro\/2023081\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,21]],"date-time":"2024-10-21T20:03:24Z","timestamp":1729541004000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.rairo-ro.org\/10.1051\/ro\/2023081"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,5]]},"references-count":49,"journal-issue":{"issue":"3"},"alternative-id":["ro230220"],"URL":"https:\/\/doi.org\/10.1051\/ro\/2023081","relation":{},"ISSN":["0399-0559","2804-7303"],"issn-type":[{"type":"print","value":"0399-0559"},{"type":"electronic","value":"2804-7303"}],"subject":[],"published":{"date-parts":[[2023,5]]}}}