{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,13]],"date-time":"2026-05-13T00:57:45Z","timestamp":1778633865832,"version":"3.51.4"},"reference-count":13,"publisher":"EDP Sciences","issue":"3","license":[{"start":{"date-parts":[[2024,5,24]],"date-time":"2024-05-24T00:00:00Z","timestamp":1716508800000},"content-version":"vor","delay-in-days":23,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["RAIRO-Oper. Res."],"accepted":{"date-parts":[[2024,3,24]]},"published-print":{"date-parts":[[2024,5]]},"abstract":"<jats:p>A Roman {2}-dominating function (Rom2DF) on a graph <jats:italic>G<\/jats:italic>(<jats:italic>V, E<\/jats:italic>) is a function <jats:italic>g<\/jats:italic> : <jats:italic>V<\/jats:italic> \u2192 {0, 1, 2} of <jats:italic>G<\/jats:italic> such that for every vertex <jats:italic>x<\/jats:italic> \u2208 <jats:italic>V<\/jats:italic> with <jats:italic>g<\/jats:italic>(<jats:italic>x<\/jats:italic>) = 0, either there exists a neighbor <jats:italic>y<\/jats:italic> of <jats:italic>x<\/jats:italic> with <jats:italic>g<\/jats:italic>(<jats:italic>y<\/jats:italic>) = 2 or at least two neighbors, <jats:italic>u, v<\/jats:italic> with <jats:italic>g<\/jats:italic>(<jats:italic>u<\/jats:italic>) = <jats:italic>g<\/jats:italic>(<jats:italic>v<\/jats:italic>) = 1. The value <jats:italic>w<\/jats:italic>(<jats:italic>g<\/jats:italic>) = \u2211<jats:sub><jats:italic>x<\/jats:italic>\u2208<jats:italic>V<\/jats:italic><\/jats:sub> <jats:italic>g<\/jats:italic>(<jats:italic>x<\/jats:italic>) is the weight of the Rom2DF. The minimum weight of a Rom2DF of <jats:italic>G<\/jats:italic> is called the <jats:italic>Roman<\/jats:italic> {2}-<jats:italic>domination number<\/jats:italic> denoted by <jats:italic>\u03b3<\/jats:italic><jats:sub>{<jats:italic>R<\/jats:italic>2}<\/jats:sub>(<jats:italic>G<\/jats:italic>). Since determining <jats:italic>\u03b3<\/jats:italic><jats:sub>{<jats:italic>R<\/jats:italic><jats:sub>2<\/jats:sub>}<\/jats:sub>(<jats:italic>G<\/jats:italic>) of a graph <jats:italic>G<\/jats:italic> is NP-hard and no metaheuristic algorithms have been proposed for the same, two procedures based on genetic algorithm are proposed as a solution for the Roman {2}-domination problem. One of the proposed methods employs a random initial population, while the other uses a population generated using heuristics. Experiments have been carried out on graphs generated using <jats:italic>Erd\u00f6s\u2013R\u00e9nyi<\/jats:italic> model, a popular model for graph generation and <jats:italic>Harwell Boeing<\/jats:italic> (HB) dataset. The experimental results demonstrate that both approaches provide a near optimal solution which is well within the known lower and upper bounds for the problem. The experimental results further show that the procedure based on random initial population has outperformed the heuristic based procedure.<\/jats:p>","DOI":"10.1051\/ro\/2024074","type":"journal-article","created":{"date-parts":[[2024,3,26]],"date-time":"2024-03-26T09:08:41Z","timestamp":1711444121000},"page":"2107-2121","source":"Crossref","is-referenced-by-count":4,"title":["Metaheuristic algorithms for solving roman {2}-domination problem"],"prefix":"10.1051","volume":"58","author":[{"given":"M. Alfred","family":"Raju","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0972-1141","authenticated-orcid":false,"given":"P. Venkata Subba","family":"Reddy","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"250","published-online":{"date-parts":[[2024,5,24]]},"reference":[{"key":"R1","unstructured":"Wu J. and Li H., Domination and its applications in ad hoc wireless networks with unidirectional links, in Proceedings of International Conference on Parallel Processing. IEEE (2000) 189\u2013197."},{"key":"R2","doi-asserted-by":"crossref","unstructured":"Cockayne E.J., Dreyer P.A., Hedetniemi S.M. and Hedetniemi S.T., Roman domination in graphs. Discrete Math. 278 (2004) 11\u201322.","DOI":"10.1016\/j.disc.2003.06.004"},{"key":"R3","doi-asserted-by":"crossref","unstructured":"Chellali M., Haynes T.W., Hedetniemi S.T. and McRae A.A., Roman 2-domination in graphs. Discrete Appl. Math. 204 (2016) 22\u201328.","DOI":"10.1016\/j.dam.2015.11.013"},{"key":"R4","doi-asserted-by":"crossref","unstructured":"Hajibaba M. and Rad N.J., Some notes on the Roman domination number and Italian domination number in graphs. J. Phys.: Conf. Ser. 890 (2017) 012123.","DOI":"10.1088\/1742-6596\/890\/1\/012123"},{"key":"R5","doi-asserted-by":"crossref","unstructured":"Haynes T.W., Hedetniemi S. and Slater P., Fundamentals of Domination in Graphs. CRC Press (1998).","DOI":"10.1002\/(SICI)1097-0037(199810)32:3<199::AID-NET4>3.0.CO;2-F"},{"key":"R6","doi-asserted-by":"crossref","first-page":"714","DOI":"10.3390\/math7080714","volume":"7","author":"Gao","year":"2019","journal-title":"Mathematics"},{"key":"R7","doi-asserted-by":"crossref","unstructured":"Varghese J. and Lakshmanan S. Aparna, Italian domination on Mycielskian and Sierpinski graphs. Discrete Math. Algorithms App. 13 (2021) 2150037.","DOI":"10.1142\/S1793830921500373"},{"key":"R8","doi-asserted-by":"crossref","unstructured":"Chellali M., Rad N. Jafari, Sheikholeslami S.M. and Volkmann L., Varieties of Roman domination II. AKCE Int. J. Graphs Comb. 17 (2020) 966\u2013984.","DOI":"10.1016\/j.akcej.2019.12.001"},{"key":"R9","doi-asserted-by":"crossref","unstructured":"Padamutham C. and Palagiri V.S.R., Complexity of Roman {2}-domination and the double Roman domination in graphs. AKCE Int. J. Graphs Comb. 17 (2020) 1081\u20131086.","DOI":"10.1016\/j.akcej.2020.01.005"},{"key":"R10","doi-asserted-by":"crossref","unstructured":"Khandelwal A., Srivastava K. and Saran G., On Roman domination of graphs using a genetic algorithm, in Proceedings of International Conference on Computational Methods and Data Engineering, ICMDE. Vol. 1. Springer Singapore (2020) 133\u2013147.","DOI":"10.1007\/978-981-15-6876-3_11"},{"key":"R11","doi-asserted-by":"crossref","unstructured":"Kimbrough S.O., Koehler G.J., Lu M. and Wood D.H., On a feasible\u2013infeasible two-population (fi-2pop) genetic algorithm for constrained optimization: distance tracing and no free lunch. Eur. J. Oper. Res. 190 (2008) 310\u2013327.","DOI":"10.1016\/j.ejor.2007.06.028"},{"key":"R12","doi-asserted-by":"crossref","unstructured":"Tang K.S., Man K.F., Kwong S. and He Q., Genetic algorithms and their applications. IEEE Signal Process. Mag. 13 (1996) 22\u201337.","DOI":"10.1109\/79.543973"},{"key":"R13","doi-asserted-by":"crossref","unstructured":"Gao H., Feng T. and Yang Y., Italian domination in the Cartesian product of paths. J. Comb. Optim. 41 (2021) 526\u2013543.","DOI":"10.1007\/s10878-020-00694-x"}],"container-title":["RAIRO - Operations Research"],"original-title":[],"link":[{"URL":"https:\/\/www.rairo-ro.org\/10.1051\/ro\/2024074\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,5,24]],"date-time":"2024-05-24T08:09:27Z","timestamp":1716538167000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.rairo-ro.org\/10.1051\/ro\/2024074"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,5]]},"references-count":13,"journal-issue":{"issue":"3"},"alternative-id":["ro230413"],"URL":"https:\/\/doi.org\/10.1051\/ro\/2024074","relation":{},"ISSN":["0399-0559","2804-7303"],"issn-type":[{"value":"0399-0559","type":"print"},{"value":"2804-7303","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,5]]}}}