{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,5]],"date-time":"2026-06-05T03:04:29Z","timestamp":1780628669700,"version":"3.54.1"},"reference-count":36,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2026,3,29]],"date-time":"2026-03-29T00:00:00Z","timestamp":1774742400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2026,3,29]],"date-time":"2026-03-29T00:00:00Z","timestamp":1774742400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100005711","name":"Universit\u00e4t Hamburg","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100005711","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Heuristics"],"published-print":{"date-parts":[[2026,6]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>This paper introduces a metaheuristic approach for solving the Maximum Disjoint Dominating Sets Problem (MDDSP). The problem is initially addressed using a Greedy Randomized Adaptive Search Procedure (GRASP), which incorporates two distinct local search strategies. The first employs a standard swap neighborhood, while the second utilizes a novel neighborhood structure designed to complement and enhance the effectiveness of the swap-based approach. To further improve performance, the GRASP is extended into the Fixed Set Search (FSS) metaheuristic, which integrates a learning mechanism to guide the search process. Computational experiments are conducted on various graph types, including random, Watts\u2013Strogatz, and Barab\u00e1si\u2013Albert graphs, with up to 1,000 vertices and differing densities. The results show that the FSS significantly outperforms state-of-the-art methods, such as the multi-constructor Construct, Merge, Solve, and Adapt (CMSA) algorithm, delivering superior solution quality across nearly all test instances. The enhanced local search techniques proved particularly effective on dense graphs. Furthermore, the results confirm that the FSS consistently improves the performance of the underlying GRASP, highlighting its robustness and efficiency for solving the MDDSP.<\/jats:p>","DOI":"10.1007\/s10732-026-09587-4","type":"journal-article","created":{"date-parts":[[2026,3,29]],"date-time":"2026-03-29T14:47:49Z","timestamp":1774795669000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Extending GRASP towards an improved Fixed Set Search for solving the maximum disjoint dominating sets problem"],"prefix":"10.1007","volume":"32","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8167-1516","authenticated-orcid":false,"given":"Raka","family":"Jovanovic","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1296-4221","authenticated-orcid":false,"given":"Stefan","family":"Vo\u00df","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2026,3,29]]},"reference":[{"key":"9587_CR1","doi-asserted-by":"publisher","DOI":"10.1016\/j.engappai.2022.105053","volume":"114","author":"SA Abed","year":"2022","unstructured":"Abed, S.A., Rais, H.M., Watada, J., Sabar, N.R.: A hybrid local search algorithm for minimum dominating set problems. Eng. Appl. Artif. Intell. 114, 105053 (2022). https:\/\/doi.org\/10.1016\/j.engappai.2022.105053","journal-title":"Eng. Appl. Artif. Intell."},{"issue":"4","key":"9587_CR2","doi-asserted-by":"publisher","first-page":"393","DOI":"10.1016\/S1389-1286(01)00302-4","volume":"38","author":"I Akyildiz","year":"2002","unstructured":"Akyildiz, I., Su, W., Sankarasubramaniam, Y., Cayirci, E.: Wireless sensor networks: a survey. Comput. Netw. 38(4), 393\u2013422 (2002)","journal-title":"Comput. Netw."},{"issue":"6","key":"9587_CR3","doi-asserted-by":"publisher","first-page":"170","DOI":"10.3390\/a14060170","volume":"14","author":"S Balbal","year":"2021","unstructured":"Balbal, S., Bouamama, S., Blum, C.: A greedy heuristic for maximizing the lifetime of wireless sensor networks based on disjoint weighted dominating sets. Algorithms 14(6), 170 (2021). https:\/\/doi.org\/10.3390\/a14060170","journal-title":"Algorithms"},{"issue":"5439","key":"9587_CR4","doi-asserted-by":"publisher","first-page":"509","DOI":"10.1126\/science.286.5439.509","volume":"286","author":"AL Barab\u00e1si","year":"1999","unstructured":"Barab\u00e1si, A.L., Albert, R.: Emergence of scaling in random networks. Science 286(5439), 509\u2013512 (1999). https:\/\/doi.org\/10.1126\/science.286.5439.509","journal-title":"Science"},{"key":"9587_CR5","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. Math. Comput. Simul. 207, 41\u201358 (2023)","journal-title":"Math. Comput. Simul."},{"issue":"3","key":"9587_CR6","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1002\/net.3230070305","volume":"7","author":"EJ Cockayne","year":"1977","unstructured":"Cockayne, E.J., Hedetniemi, S.T.: Towards a theory of domination in graphs. Networks 7(3), 247\u2013261 (1977). https:\/\/doi.org\/10.1002\/net.3230070305","journal-title":"Networks"},{"issue":"4","key":"9587_CR7","doi-asserted-by":"publisher","first-page":"1019","DOI":"10.1137\/050636589","volume":"21","author":"M Dror","year":"2008","unstructured":"Dror, M., Orlin, J.B.: Combinatorial optimization with explicit delineation of the ground set by a collection of subsets. SIAM J. Discret. Math. 21(4), 1019\u20131034 (2008). https:\/\/doi.org\/10.1137\/050636589","journal-title":"SIAM J. Discret. Math."},{"key":"9587_CR8","doi-asserted-by":"crossref","unstructured":"Feige, U., Halld\u00f3rsson, M.M., Kortsarz, G.: Approximating the domatic number. In: Proceedings of the thirty-second annual ACM symposium on Theory of computing. pp. 134\u2013143 (2000)","DOI":"10.1145\/335305.335321"},{"issue":"2","key":"9587_CR9","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.: Greedy randomized adaptive search procedures. J. Global Optim. 6(2), 109\u2013133 (1995)","journal-title":"J. Global Optim."},{"key":"9587_CR10","doi-asserted-by":"publisher","unstructured":"Hammersley, J.M., Handscomb, D.C.: Percolation Processes, pp. 134\u2013141. Springer, Netherlands, Dordrecht (1964). https:\/\/doi.org\/10.1007\/978-94-009-5819-7_11","DOI":"10.1007\/978-94-009-5819-7_11"},{"key":"9587_CR11","doi-asserted-by":"publisher","unstructured":"Islam, K., Akl, S.G., Meijer, H.: Maximizing the lifetime of wireless sensor networks through domatic partition. In: 2009 IEEE 34th Conference on Local Computer Networks. pp. 436\u2013442 (2009). https:\/\/doi.org\/10.1109\/LCN.2009.5355161","DOI":"10.1109\/LCN.2009.5355161"},{"key":"9587_CR12","doi-asserted-by":"publisher","unstructured":"Jovanovic, R., Bayhan, S., Vo\u00df, S.: Matheuristic fixed set search applied to electric bus fleet scheduling. In: International Conference on Learning and Intelligent Optimization. pp. 393\u2013407. Springer (2023). https:\/\/doi.org\/10.1007\/978-3-031-44505-7_27","DOI":"10.1007\/978-3-031-44505-7_27"},{"key":"9587_CR13","doi-asserted-by":"publisher","first-page":"481","DOI":"10.1007\/s10732-022-09499-z","volume":"28","author":"R Jovanovic","year":"2022","unstructured":"Jovanovic, R., Sanfilippo, A.P., Vo\u00df, S.: Fixed set search applied to the multi-objective minimum weighted vertex cover problem. Journal of Heuristics 28, 481\u2013508 (2022). https:\/\/doi.org\/10.1007\/s10732-022-09499-z","journal-title":"Journal of Heuristics"},{"issue":"1","key":"9587_CR14","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1016\/j.ejor.2023.01.044","volume":"309","author":"R Jovanovic","year":"2023","unstructured":"Jovanovic, R., Sanfilippo, A.P., Vo\u00df, S.: Fixed set search applied to the clique partitioning problem. Eur. J. Oper. Res. 309(1), 65\u201381 (2023). https:\/\/doi.org\/10.1016\/j.ejor.2023.01.044","journal-title":"Eur. J. Oper. Res."},{"key":"9587_CR15","doi-asserted-by":"publisher","unstructured":"Jovanovic, R., Tuba, M., Vo\u00df, S.: Fixed set search applied to the traveling salesman problem. In: International Workshop on Hybrid Metaheuristics. pp. 63\u201377. Springer (2019). https:\/\/doi.org\/10.1007\/978-3-030-05983-5_5","DOI":"10.1007\/978-3-030-05983-5_5"},{"key":"9587_CR16","doi-asserted-by":"publisher","unstructured":"Jovanovic, R., Vo\u00df, S.: Fixed set search applied to the minimum weighted vertex cover problem. In: International Symposium on Experimental Algorithms. pp. 490\u2013504. Springer (2019). https:\/\/doi.org\/10.1007\/978-3-030-34029-2_31","DOI":"10.1007\/978-3-030-34029-2_31"},{"key":"9587_CR17","doi-asserted-by":"publisher","unstructured":"Jovanovic, R., Voss, S.: The fixed set search applied to the power dominating set problem. Expert. Syst. 37(6), e12559 (2020). https:\/\/doi.org\/10.1111\/exsy.12559","DOI":"10.1111\/exsy.12559"},{"key":"9587_CR18","doi-asserted-by":"publisher","unstructured":"Jovanovic, R., Vo\u00df, S.: Fixed set search applied to the maximum disjoint dominating sets problem. In: Sevaux, M., Olteanu, A.L., Pardo, E.G., Sifaleras, A., Makboul, S. (eds.) Metaheuristics. pp. 347\u2013353. Springer, Cham (2024). https:\/\/doi.org\/10.1007\/978-3-031-62922-8_26","DOI":"10.1007\/978-3-031-62922-8_26"},{"key":"9587_CR19","doi-asserted-by":"publisher","first-page":"1329","DOI":"10.1007\/s00291-024-00746-2","volume":"46","author":"R Jovanovic","year":"2024","unstructured":"Jovanovic, R., Vo\u00df, S.: Matheuristic fixed set search applied to the multidimensional knapsack problem and the knapsack problem with forfeit sets. OR Spectrum 46, 1329\u20131365 (2024). https:\/\/doi.org\/10.1007\/s00291-024-00746-2","journal-title":"OR Spectrum"},{"key":"9587_CR20","doi-asserted-by":"publisher","unstructured":"Jovanovic, R., Vo\u00df, S.: Fixed set search application for minimizing the makespan on unrelated parallel machines with sequence-dependent setup times. Appl. Soft Comput. 110, 107521 (2021) https:\/\/doi.org\/10.1016\/j.asoc.2021.107521","DOI":"10.1016\/j.asoc.2021.107521"},{"key":"9587_CR21","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1007\/s00153-013-0359-2","volume":"53","author":"M Jura","year":"2014","unstructured":"Jura, M., Levin, O., Markkanen, T.: Domatic partitions of computable graphs. Arch. Math. Logic 53, 137\u2013155 (2014)","journal-title":"Arch. Math. Logic"},{"issue":"4","key":"9587_CR22","doi-asserted-by":"publisher","first-page":"640","DOI":"10.3390\/math10040640","volume":"10","author":"M Landete","year":"2022","unstructured":"Landete, M., Sainz-Pardo, J.L.: The domatic partition problem in separable graphs. Mathematics 10(4), 640 (2022). https:\/\/doi.org\/10.3390\/math10040640","journal-title":"Mathematics"},{"key":"9587_CR23","doi-asserted-by":"publisher","unstructured":"Maniezzo, V., St\u00fctzle, T., Vo\u00df, S. (eds.): Matheuristics. Springer (2010). https:\/\/doi.org\/10.1007\/978-1-4419-1306-7","DOI":"10.1007\/978-1-4419-1306-7"},{"key":"9587_CR24","doi-asserted-by":"crossref","unstructured":"Mesbahi, M., Egestedt, M.: Graph theoretic methods in multiagent networks. Princeton University Press (2010)","DOI":"10.1515\/9781400835355"},{"key":"9587_CR25","doi-asserted-by":"publisher","unstructured":"Nemhauser, G., Wolsey, L.: The Scope of Integer and Combinatorial Optimization, chap. I.1, pp. 1\u201326. John Wiley & Sons (1988). https:\/\/doi.org\/10.1002\/9781118627372.ch1","DOI":"10.1002\/9781118627372.ch1"},{"key":"9587_CR26","doi-asserted-by":"crossref","unstructured":"Pandit, S., Pemmaraju, S.V., Varadarajan, K.: Approximation algorithms for domatic partitions of unit disk graphs. In: Dinur, I., Jansen, K., Naor, J., Rolim, J. (eds.) Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. pp. 312\u2013325. Springer, Berlin, Heidelberg (2009)","DOI":"10.1007\/978-3-642-03685-9_24"},{"key":"9587_CR27","doi-asserted-by":"publisher","unstructured":"Poon, S.H., Yen, W.C.K., Ung, C.T.: Domatic partition on several classes of graphs. In: Lin, G. (ed.) Combinatorial Optimization and Applications. pp. 245\u2013256. Springer, Berlin, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-31770-5_22","DOI":"10.1007\/978-3-642-31770-5_22"},{"key":"9587_CR28","doi-asserted-by":"publisher","unstructured":"Rosati, R.M., Bouamama, S., Blum, C.: Construct, merge, solve and adapt applied to the maximum disjoint dominating sets problem. In: Di Gaspero, L., Festa, P., Nakib, A., Pavone, M. (eds.) Metaheuristics, pp. 306\u2013321. Springer International Publishing, Cham (2023). https:\/\/doi.org\/10.1007\/978-3-031-26504-4_22","DOI":"10.1007\/978-3-031-26504-4_22"},{"key":"9587_CR29","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2023.106450","volume":"161","author":"RM Rosati","year":"2024","unstructured":"Rosati, R.M., Bouamama, S., Blum, C.: Multi-constructor CMSA for the maximum disjoint dominating sets problem. Computers & Operations Research 161, 106450 (2024). https:\/\/doi.org\/10.1016\/j.cor.2023.106450","journal-title":"Computers & Operations Research"},{"key":"9587_CR30","doi-asserted-by":"publisher","unstructured":"Sondergeld, L., Vo\u00df, S.: Cooperative intelligent search using adaptive memory techniques. In: Vo\u00df, S., Martello, S., Osman, I., Roucairol, C. (eds.) Meta-Heuristics: Advances and Trends in Local Search Paradigms for Optimization, pp. 297\u2013312. Kluwer, Boston (1999). https:\/\/doi.org\/10.1007\/978-1-4615-5775-3_21","DOI":"10.1007\/978-1-4615-5775-3_21"},{"key":"9587_CR31","doi-asserted-by":"publisher","unstructured":"Taillard, E., Vo\u00df, S.: POPMUSIC - A partial optimization metaheuristic under special intensification conditions. In: Ribeiro, C., Hansen, P. (eds.) Essays and Surveys in Metaheuristics, pp. 613\u2013629. Kluwer, Boston (2002). https:\/\/doi.org\/10.1007\/978-1-4615-1507-4_27","DOI":"10.1007\/978-1-4615-1507-4_27"},{"key":"9587_CR32","first-page":"335","volume-title":"Network Design: Connectivity and Facilities Location, DIMACS Series in Discrete Mathematics and Theoretical Computer Science","author":"S Vo\u00df","year":"1998","unstructured":"Vo\u00df, S., Gutenschwager, K.: A chunking based genetic algorithm for the Steiner tree problem in graphs. In: Pardalos, P., Du, D.Z. (eds.) Network Design: Connectivity and Facilities Location, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 40, pp. 335\u2013355. Princeton, AMS (1998)"},{"key":"9587_CR33","doi-asserted-by":"publisher","unstructured":"Watson, J.P.: An introduction to fitness landscape analysis and cost models for local search. In: Handbook of Metaheuristics, chap. 20, pp. 599\u2013623. Springer (2010). https:\/\/doi.org\/10.1007\/978-1-4419-1665-5_20","DOI":"10.1007\/978-1-4419-1665-5_20"},{"key":"9587_CR34","doi-asserted-by":"publisher","unstructured":"Watts, D.J., Strogatz, S.H.: Collective dynamics of small-world networks. Nature 393(6684), 440\u2013442 (1998). https:\/\/doi.org\/10.1038\/30918","DOI":"10.1038\/30918"},{"key":"9587_CR35","doi-asserted-by":"publisher","unstructured":"Woodruff, D.: Proposals for chunking and tabu search. Eur. J. Oper. Res. 106, 585\u2013598 (1998). https:\/\/doi.org\/10.1016\/S0377-2217(97)00293-2","DOI":"10.1016\/S0377-2217(97)00293-2"},{"key":"9587_CR36","doi-asserted-by":"publisher","first-page":"186","DOI":"10.1016\/j.jnca.2013.02.025","volume":"37","author":"J Yu","year":"2014","unstructured":"Yu, J., Zhang, Q., Yu, D., Chen, C., Wang, G.: Domatic partition in homogeneous wireless sensor networks. J. Netw. Comput. Appl. 37, 186\u2013193 (2014)","journal-title":"J. Netw. Comput. Appl."}],"container-title":["Journal of Heuristics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10732-026-09587-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10732-026-09587-4","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10732-026-09587-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,5]],"date-time":"2026-06-05T02:19:27Z","timestamp":1780625967000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10732-026-09587-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,3,29]]},"references-count":36,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,6]]}},"alternative-id":["9587"],"URL":"https:\/\/doi.org\/10.1007\/s10732-026-09587-4","relation":{},"ISSN":["1381-1231","1572-9397"],"issn-type":[{"value":"1381-1231","type":"print"},{"value":"1572-9397","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,3,29]]},"assertion":[{"value":"23 January 2025","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 February 2026","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 February 2026","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 March 2026","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that there is no competing financial interest or personal relationship that could have appeared to influence this paper and its results.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflicts of Interest"}},{"value":"This research upholds ethical standards by ensuring that all data utilized are sourced from secondary sources and are publicly available. As such, no ethical approval was required for this study.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethical Approval"}}],"article-number":"15"}}