{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T02:01:21Z","timestamp":1761616881453,"version":"build-2065373602"},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2025,5,26]],"date-time":"2025-05-26T00:00:00Z","timestamp":1748217600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,5,26]],"date-time":"2025-05-26T00:00:00Z","timestamp":1748217600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Universitat de Valencia"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Prog. Comp."],"published-print":{"date-parts":[[2025,12]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>We propose a reference framework to apply the multiparent path relinking (MPR) methodology. MPR is an extension of path relinking (PR) that has been proposed and described but, to the best of our knowledge, it has never been applied. PR is a trajectory-based neighborhood search strategy that explores paths that traverse pairs of solutions. PR has been widely used for search intensification purposes within metaheuristic implementations. To show how MPR can be embedded in more than one setting, our proposal consists of both employing MPR as a post-processing step in a greedy randomized adaptive search procedure (GRASP) and as the combination method in a scatter search (SS). We use the power dominating set problem (PDSP) as our testing platform because its difficulty and structure enable the design and assessment of various strategies. The PDSP seeks to find the minimum placement of measurement devices in an electrical network to monitor the entire system. Our computational experiments are designed to identify the contribution of each element of our proposed MRP implementations.<\/jats:p>","DOI":"10.1007\/s12532-025-00286-y","type":"journal-article","created":{"date-parts":[[2025,5,26]],"date-time":"2025-05-26T02:00:01Z","timestamp":1748224801000},"page":"759-779","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Multiparent path relinking. An application to the power dominating set problem"],"prefix":"10.1007","volume":"17","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9396-5375","authenticated-orcid":false,"given":"R.","family":"Mart\u00edn-Santamar\u00eda","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9995-010X","authenticated-orcid":false,"given":"A.","family":"Mart\u00ednez-Gavara","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3022-3865","authenticated-orcid":false,"given":"A. D.","family":"L\u00f3pez-S\u00e1nchez","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8759-5523","authenticated-orcid":false,"given":"M.","family":"Laguna","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,5,26]]},"reference":[{"issue":"11","key":"286_CR1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2022.113113","volume":"345","author":"SE Anderson","year":"2022","unstructured":"Anderson, S.E., Kuenzel, K.: Power domination in cubic graphs and cartesian products. Discrete Mathematics 345(11), 113113 (2022). https:\/\/doi.org\/10.1016\/j.disc.2022.113113","journal-title":"Discrete Mathematics"},{"key":"286_CR2","doi-asserted-by":"publisher","first-page":"344","DOI":"10.1007\/s00453-024-01283-8","volume":"87","author":"T Bl\u00e4sius","year":"2025","unstructured":"Bl\u00e4sius, T., G\u00f6ttlicher, M.: An efficient algorithm for power dominating set. Algorithmica 87, 344\u2013376 (2025). https:\/\/doi.org\/10.1007\/s00453-024-01283-8","journal-title":"Algorithmica"},{"issue":"12","key":"286_CR3","doi-asserted-by":"publisher","first-page":"1800","DOI":"10.1057\/jors.2013.156","volume":"65","author":"V Campos","year":"2014","unstructured":"Campos, V., Mart\u00ed, R., S\u00e1nchez-Oro, J., Duarte, A.: GRASP with path relinking for the orienteering problem. Journal of the Operational Research Society 65(12), 1800\u20131813 (2014). https:\/\/doi.org\/10.1057\/jors.2013.156","journal-title":"Journal of the Operational Research Society"},{"key":"286_CR4","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1016\/j.matcom.2022.12.018","volume":"207","author":"A Casado","year":"2023","unstructured":"Casado, A., Bermudo, S., L\u00f3pez-S\u00e1nchez, A., S\u00e1nchez-Oro, J.: An iterated greedy algorithm for finding the minimum dominating set in graphs. Mathematics and Computers in Simulation 207, 41\u201358 (2023). https:\/\/doi.org\/10.1016\/j.matcom.2022.12.018","journal-title":"Mathematics and Computers in Simulation"},{"key":"286_CR5","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1016\/j.ins.2017.10.033","volume":"426","author":"D Chalupa","year":"2018","unstructured":"Chalupa, D.: An order-based algorithm for minimum dominating set with application in graph mining. Information Sciences 426, 101\u2013116 (2018). https:\/\/doi.org\/10.1016\/j.ins.2017.10.033","journal-title":"Information Sciences"},{"issue":"11","key":"286_CR6","doi-asserted-by":"publisher","first-page":"1191","DOI":"10.1016\/j.patrec.2005.07.017","volume":"27","author":"O Cord\u00f3n","year":"2006","unstructured":"Cord\u00f3n, O., Damas, S., Santamar\u00eda, J.: A fast and accurate approach for 3D image registration using the scatter search evolutionary algorithm. Pattern Recognition Letters 27(11), 1191\u20131200 (2006). https:\/\/doi.org\/10.1016\/j.patrec.2005.07.017","journal-title":"Pattern Recognition Letters"},{"issue":"6","key":"286_CR7","doi-asserted-by":"publisher","first-page":"1023","DOI":"10.1016\/j.dam.2005.08.006","volume":"154","author":"M Dorfling","year":"2006","unstructured":"Dorfling, M., Henning, M.A.: A note on power domination in grid graphs. Discrete Applied Mathematics 154(6), 1023\u20131027 (2006). https:\/\/doi.org\/10.1016\/j.dam.2005.08.006","journal-title":"Discrete Applied Mathematics"},{"issue":"2","key":"286_CR8","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1007\/bf01096763","volume":"6","author":"TA Feo","year":"1995","unstructured":"Feo, T.A., Resende, M.G.C.: Greedy randomized adaptive search procedures. Journal of Global Optimization 6(2), 109\u2013133 (1995). https:\/\/doi.org\/10.1007\/bf01096763","journal-title":"Journal of Global Optimization"},{"issue":"3","key":"286_CR9","doi-asserted-by":"publisher","first-page":"190","DOI":"10.1287\/ijoc.1.3.190","volume":"1","author":"F Glover","year":"1989","unstructured":"Glover, F.: Tabu search - Part I. INFORMS Journal on Computing 1(3), 190\u2013206 (1989). https:\/\/doi.org\/10.1287\/ijoc.1.3.190","journal-title":"INFORMS Journal on Computing"},{"key":"286_CR10","first-page":"653","volume":"29","author":"F Glover","year":"2000","unstructured":"Glover, F., Laguna, M., Mart\u00ed, R.: Fundamentals of scatter search and path relinking. Control and Cybernetics 29, 653\u2013684 (2000)","journal-title":"Control and Cybernetics"},{"issue":"4","key":"286_CR11","doi-asserted-by":"publisher","first-page":"519","DOI":"10.1137\/s0895480100375831","volume":"15","author":"TW Haynes","year":"2002","unstructured":"Haynes, T.W., Hedetniemi, S.M., Hedetniemi, S.T., Henning, M.A.: Domination in graphs applied to electric power networks. SIAM Journal on Discrete Mathematics 15(4), 519\u2013529 (2002). https:\/\/doi.org\/10.1137\/s0895480100375831","journal-title":"SIAM Journal on Discrete Mathematics"},{"issue":"6","key":"286_CR12","doi-asserted-by":"publisher","DOI":"10.1111\/exsy.12559","volume":"37","author":"R Jovanovic","year":"2020","unstructured":"Jovanovic, R., Voss, S.: The fixed set search applied to the power dominating set problem. Expert Systems 37(6), e12559 (2020). https:\/\/doi.org\/10.1111\/exsy.12559","journal-title":"Expert Systems"},{"issue":"1","key":"286_CR13","doi-asserted-by":"publisher","first-page":"44","DOI":"10.1287\/ijoc.11.1.44","volume":"11","author":"M Laguna","year":"1999","unstructured":"Laguna, M., Mart\u00ed, R.: GRASP and path relinking for 2-layer straight line crossing minimization. INFORMS Journal on Computing 11(1), 44\u201352 (1999). https:\/\/doi.org\/10.1287\/ijoc.11.1.44","journal-title":"INFORMS Journal on Computing"},{"key":"286_CR14","doi-asserted-by":"crossref","unstructured":"Laguna, M., Mart\u00ed, R.: Scatter search: methodology and implementations in C. Springer, New York (2003)","DOI":"10.1007\/978-1-4615-0337-8"},{"issue":"1","key":"286_CR15","doi-asserted-by":"publisher","first-page":"1059","DOI":"10.1007\/s00521-016-2429-y","volume":"28","author":"R Li","year":"2016","unstructured":"Li, R., Hu, S., Gao, J., Zhou, Y., Wang, Y., Yin, M.: GRASP for connected dominating set problems. Neural Computing and Applications 28(1), 1059\u20131067 (2016). https:\/\/doi.org\/10.1007\/s00521-016-2429-y","journal-title":"Neural Computing and Applications"},{"key":"286_CR16","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1016\/j.cor.2018.12.017","volume":"104","author":"A L\u00f3pez-S\u00e1nchez","year":"2019","unstructured":"L\u00f3pez-S\u00e1nchez, A., S\u00e1nchez-Oro, J., Hern\u00e1ndez-D\u00edaz, A.: GRASP and VNS for solving the p-next center problem. Computers & Operations Research 104, 295\u2013303 (2019)","journal-title":"Computers & Operations Research"},{"issue":"1","key":"286_CR17","doi-asserted-by":"publisher","first-page":"54","DOI":"10.1016\/j.ejor.2014.06.042","volume":"240","author":"R Mart\u00ed","year":"2015","unstructured":"Mart\u00ed, R., Campos, V., Resende, M.G., Duarte, A.: Multiobjective GRASP with path relinking. European Journal of Operational Research 240(1), 54\u201371 (2015). https:\/\/doi.org\/10.1016\/j.ejor.2014.06.042","journal-title":"European Journal of Operational Research"},{"issue":"1","key":"286_CR18","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1162\/evco_a_00317","volume":"32","author":"R Mart\u00edn-Santamar\u00eda","year":"2024","unstructured":"Mart\u00edn-Santamar\u00eda, R., Cavero, S., Herr\u00e1n, A., Duarte, A., Colmenar, J.M.: A practical methodology for reproducible experimentation: An application to the double-row facility layout problem. Evolutionary Computation 32(1), 69\u2013104 (2024). https:\/\/doi.org\/10.1162\/evco_a_00317","journal-title":"Evolutionary Computation"},{"key":"286_CR19","doi-asserted-by":"publisher","DOI":"10.5281\/zenodo.10015214","author":"R Mart\u00edn-Santamar\u00eda","year":"2025","unstructured":"Mart\u00edn-Santamar\u00eda, R., Mart\u00ednez-Gavara, A., L\u00f3pez-S\u00e1nchez, A.D., Laguna, M.: Code for Multiparent path relinking. An application to the power dominating set problem. (2025). https:\/\/doi.org\/10.5281\/zenodo.10015214","journal-title":"An application to the power dominating set problem."},{"issue":"2","key":"286_CR20","first-page":"3326","volume":"13","author":"R Prabha","year":"2022","unstructured":"Prabha, R., Thenmozhi, B.: Power domination number of some convex polytopes. Journal of Algebraic statistics 13(2), 3326\u20133332 (2022)","journal-title":"Journal of Algebraic statistics"},{"issue":"2","key":"286_CR21","doi-asserted-by":"publisher","first-page":"498","DOI":"10.1016\/j.cor.2008.05.011","volume":"37","author":"M Resende","year":"2010","unstructured":"Resende, M., Mart\u00ed, R., Gallego, M., Duarte, A.: GRASP and path relinking for the max-min diversity problem. Computers & Operations Research 37(2), 498\u2013508 (2010)","journal-title":"Computers & Operations Research"},{"key":"286_CR22","doi-asserted-by":"publisher","unstructured":"Resende, M.G., Ribeiro, C.C., Glover, F., Mart\u00ed, R.: Scatter Search and Path-Relinking: Fundamentals, Advances, and Applications, pp. 87\u2013107. Springer US (2010). https:\/\/doi.org\/10.1007\/978-1-4419-1665-5_4","DOI":"10.1007\/978-1-4419-1665-5_4"},{"issue":"1","key":"286_CR23","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1023\/b:heur.0000019986.96257.50","volume":"10","author":"MG Resende","year":"2004","unstructured":"Resende, M.G., Werneck, R.F.: A hybrid heuristic for the p-median problem. Journal of Heuristics 10(1), 59\u201388 (2004). https:\/\/doi.org\/10.1023\/b:heur.0000019986.96257.50","journal-title":"Journal of Heuristics"},{"key":"286_CR24","doi-asserted-by":"publisher","unstructured":"Resende, M.G.C., Ribeiro, C.C.: Path-relinking, pp. 167\u2013188. Springer New York (2016). https:\/\/doi.org\/10.1007\/978-1-4939-6530-4_8","DOI":"10.1007\/978-1-4939-6530-4_8"},{"issue":"6","key":"286_CR25","doi-asserted-by":"publisher","first-page":"1121","DOI":"10.1080\/09720529.2019.1689610","volume":"22","author":"TN Saibavani","year":"2019","unstructured":"Saibavani, T.N., Parvathi, N.: Power domination number of sunlet graph and other graphs. Journal of Discrete Mathematical Sciences and Cryptography 22(6), 1121\u20131127 (2019). https:\/\/doi.org\/10.1080\/09720529.2019.1689610","journal-title":"Journal of Discrete Mathematical Sciences and Cryptography"},{"key":"286_CR26","doi-asserted-by":"publisher","first-page":"778","DOI":"10.1016\/j.amc.2015.01.037","volume":"256","author":"S Stephen","year":"2015","unstructured":"Stephen, S., Rajan, B., Grigorious, C., William, A.: Resolving-power dominating sets. Applied Mathematics and Computation 256, 778\u2013785 (2015). https:\/\/doi.org\/10.1016\/j.amc.2015.01.037","journal-title":"Applied Mathematics and Computation"},{"issue":"4","key":"286_CR27","doi-asserted-by":"publisher","first-page":"769","DOI":"10.1007\/s10898-016-0446-0","volume":"66","author":"J S\u00e1nchez-Oro","year":"2016","unstructured":"S\u00e1nchez-Oro, J., Laguna, M., Mart\u00ed, R., Duarte, A.: Scatter search for the bandpass problem. Journal of Global Optimization 66(4), 769\u2013790 (2016). https:\/\/doi.org\/10.1007\/s10898-016-0446-0","journal-title":"Journal of Global Optimization"},{"issue":"1","key":"286_CR28","doi-asserted-by":"publisher","first-page":"10","DOI":"10.1002\/net.21571","volume":"65","author":"J S\u00e1nchez-Oro","year":"2015","unstructured":"S\u00e1nchez-Oro, J., Laguna, M., Duarte, A., Mart\u00ed, R.: Scatter search for the profile minimization problem. Networks 65(1), 10\u201321 (2015). https:\/\/doi.org\/10.1002\/net.21571","journal-title":"Networks"},{"issue":"15","key":"286_CR29","doi-asserted-by":"publisher","first-page":"1812","DOI":"10.1016\/j.disc.2006.03.037","volume":"306","author":"M Zhao","year":"2006","unstructured":"Zhao, M., Kang, L., Chang, G.J.: Power domination in graphs. Discrete Mathematics 306(15), 1812\u20131816 (2006). https:\/\/doi.org\/10.1016\/j.disc.2006.03.037","journal-title":"Discrete Mathematics"}],"container-title":["Mathematical Programming Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s12532-025-00286-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s12532-025-00286-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s12532-025-00286-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T01:54:00Z","timestamp":1761616440000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s12532-025-00286-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,5,26]]},"references-count":29,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2025,12]]}},"alternative-id":["286"],"URL":"https:\/\/doi.org\/10.1007\/s12532-025-00286-y","relation":{},"ISSN":["1867-2949","1867-2957"],"issn-type":[{"type":"print","value":"1867-2949"},{"type":"electronic","value":"1867-2957"}],"subject":[],"published":{"date-parts":[[2025,5,26]]},"assertion":[{"value":"24 November 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 May 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 May 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have no relevant financial or non-financial interests to disclose.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing Interests"}}]}}