{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,2]],"date-time":"2026-06-02T22:15:41Z","timestamp":1780438541358,"version":"3.54.1"},"reference-count":26,"publisher":"MDPI AG","issue":"6","license":[{"start":{"date-parts":[[2024,6,12]],"date-time":"2024-06-12T00:00:00Z","timestamp":1718150400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"CCyTEM"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>A dominating set of a graph is a subset of vertices such that every vertex not in the subset has at least one neighbor within the subset. The corresponding optimization problem is known to be NP-hard. It is proved to be beneficial to separate the solution process in two stages. First, one can apply a fast greedy algorithm to obtain an initial dominating set and then use an iterative procedure to purify (reduce) the size of this dominating set. In this work, we develop the purification stage and propose new purification algorithms. The purification procedures that we present here outperform, in practice, the earlier known purification procedure. We have tested our algorithms for over 1300 benchmark problem instances. Compared to the estimations due to known upper bounds, the obtained solutions are about seven times better. Remarkably, for the 500 benchmark instances for which the optimum is known, the optimal solutions are obtained for 46.33% of the tested instances, whereas the average error for the remaining instances is about 1.01.<\/jats:p>","DOI":"10.3390\/a17060258","type":"journal-article","created":{"date-parts":[[2024,6,13]],"date-time":"2024-06-13T04:30:12Z","timestamp":1718253012000},"page":"258","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Approximating a Minimum Dominating Set by Purification"],"prefix":"10.3390","volume":"17","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7901-4936","authenticated-orcid":false,"given":"Ernesto","family":"Parra Inza","sequence":"first","affiliation":[{"name":"Centro de Investigaci\u00f3n en Ciencias, Universidad Aut\u00f3noma del Estado de Morelos, Cuernavaca 62209, Morelos, Mexico"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9013-9334","authenticated-orcid":false,"given":"Nodari","family":"Vakhania","sequence":"additional","affiliation":[{"name":"Centro de Investigaci\u00f3n en Ciencias, Universidad Aut\u00f3noma del Estado de Morelos, Cuernavaca 62209, Morelos, Mexico"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0863-4695","authenticated-orcid":false,"given":"Jos\u00e9 Mar\u00eda","family":"Sigarreta Almira","sequence":"additional","affiliation":[{"name":"Facultad de Matem\u00e1ticas, Universidad Aut\u00f3noma de Guerrero, Acapulco de Ju\u00e1rez 39650, Guerrero, Mexico"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5184-0005","authenticated-orcid":false,"given":"Jos\u00e9 Alberto","family":"Hern\u00e1ndez-Aguilar","sequence":"additional","affiliation":[{"name":"Facultad de Contadur\u00eda, Administraci\u00f3n e Inform\u00e1tica, Universidad Aut\u00f3noma del Estado de Morelos, Cuernavaca 62209, Morelos, Mexico"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"1968","published-online":{"date-parts":[[2024,6,12]]},"reference":[{"key":"ref_1","unstructured":"Garey, M.R., and Johnson, D.S. (1979). Computers and Intractability, Freeman."},{"key":"ref_2","unstructured":"Berge, C. (1962). The Theory of Graphs and Its Applications, Methuen & Co, Ltd."},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Ore, O. (1962). Theory of Graphs, AMS Colloquium Publications.","DOI":"10.1090\/coll\/038"},{"key":"ref_4","unstructured":"Haynes, T.W., Hedetniemi, S.T., and Slater, P.J. (1998). Domination in Graphs, Marcel Dekker Publications. Advanced Topics."},{"key":"ref_5","unstructured":"Haynes, T.W. (2017). Domination in Graphs, Routledge. Advanced Topics."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"105368","DOI":"10.1016\/j.cor.2021.105368","article-title":"Heuristics for k-domination models of facility location problems in street networks","volume":"133","author":"Corcoran","year":"2021","journal-title":"Comput. Oper. Res."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"352","DOI":"10.1016\/0377-2217(94)90364-6","article-title":"The k-neighbor, r-domination problems on interval graphs","volume":"79","author":"Joshi","year":"1994","journal-title":"Eur. J. Oper. Res."},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Liao, C.S., and Lee, D.T. (2005, January 16\u201319). Power domination problem in graphs. Proceedings of the International Computing and Combinatorics Conference, Kunming, China.","DOI":"10.1007\/11533719_83"},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"519","DOI":"10.1137\/S0895480100375831","article-title":"Domination in graphs applied to electric power networks","volume":"15","author":"Haynes","year":"2002","journal-title":"SIAM J. Discret. Math."},{"key":"ref_10","first-page":"3","article-title":"Robustness Analysis of Trophic Networks using Outer k-independent Total Dominant Sets","volume":"Volume 4","year":"2021","journal-title":"Modelaci\u00f3n Matem\u00e1tica IV Biomatem\u00e1ticas, Epidemiolog\u00eda, Ingenier\u00eda"},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Balasundaram, B., and Butenko, S. (2006). Graph domination, coloring and cliques in telecommunications. Handbook of Optimization in Telecommunications, Springer.","DOI":"10.1007\/978-0-387-30165-5_30"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1023\/B:MONE.0000013625.87793.13","article-title":"Distributed construction of connected dominating set in wireless ad hoc networks","volume":"9","author":"Wan","year":"2004","journal-title":"Mob. Netw. Appl."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"425","DOI":"10.1002\/wcm.125","article-title":"Power-aware broadcasting and activity scheduling in ad hoc wireless networks using connected dominating sets","volume":"3","author":"Wu","year":"2003","journal-title":"Wirel. Commun. Mob. Comput."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"866","DOI":"10.1109\/TPDS.2002.1036062","article-title":"Extended dominating-set-based routing in ad hoc wireless networks with unidirectional links","volume":"13","author":"Wu","year":"2002","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Wang, F., Camacho, E., and Xu, K. (2009, January 10\u201312). Positive influence dominating set in online social networks. Proceedings of the Combinatorial Optimization and Applications: Third International Conference, COCOA 2009, Huangshan, China. Proceedings 3.","DOI":"10.1007\/978-3-642-02026-1_29"},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1016\/j.tcs.2009.10.001","article-title":"On positive influence dominating sets in social networks","volume":"412","author":"Wang","year":"2011","journal-title":"Theor. Comput. Sci."},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Abu-Khzam, F.N., and Lamaa, K. (2018, January 15\u201319). Efficient heuristic algorithms for positive-influence dominating set in social networks. Proceedings of the IEEE INFOCOM 2018-IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS), Honolulu, HI, USA.","DOI":"10.1109\/INFCOMW.2018.8406851"},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1287\/moor.4.3.233","article-title":"A greedy heuristic for the set-covering problem","volume":"4","author":"Chvatal","year":"1979","journal-title":"Math. Oper. Res."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1016\/0020-0190(91)90021-9","article-title":"Analysis of a greedy heuristic for finding small dominating sets in graphs","volume":"39","author":"Parekh","year":"1991","journal-title":"Inf. Process. Lett."},{"key":"ref_20","unstructured":"Eubank, S., Kumar, V.A., Marathe, M.V., Srinivasan, A., and Wang, N. (2004, January 11\u201314). Structural and algorithmic aspects of massive social networks. Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, New Orleans, LA, USA."},{"key":"ref_21","unstructured":"Campan, A., Truta, T.M., and Beckerich, M. (2015, January 25\u201326). Fast Dominating Set Algorithms for Social Networks. Proceedings of the MAICS, Greensboro, NC, USA."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"142","DOI":"10.1016\/j.tcs.2022.07.020","article-title":"A polynomial-time approximation to a minimum dominating set in a graph","volume":"930","author":"Vakhania","year":"2022","journal-title":"Theor. Comput. Sci."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"2147","DOI":"10.1016\/j.dam.2011.07.001","article-title":"Exact algorithms for dominating set","volume":"159","author":"Bodlaender","year":"2011","journal-title":"Discret. Appl. Math."},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Iwata, Y. (2012, January 12\u201314). A faster algorithm for dominating set analyzed by the potential method. Proceedings of the International Symposium on Parameterized and Exact Computation, Ljubljana, Slovenia.","DOI":"10.1007\/978-3-642-28050-4_4"},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"926","DOI":"10.1016\/j.ejor.2023.08.033","article-title":"Exact and heuristic algorithms for the domination problem","volume":"313","author":"Vakhania","year":"2024","journal-title":"Eur. J. Oper. Res."},{"key":"ref_26","unstructured":"Parra Inza, E. (2024, April 03). Random Graph (1), version 5; Mendeley Data. Available online: https:\/\/data.mendeley.com\/datasets\/rr5bkj6dw5\/5."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/17\/6\/258\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T14:57:29Z","timestamp":1760108249000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/17\/6\/258"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,6,12]]},"references-count":26,"journal-issue":{"issue":"6","published-online":{"date-parts":[[2024,6]]}},"alternative-id":["a17060258"],"URL":"https:\/\/doi.org\/10.3390\/a17060258","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,6,12]]}}}