{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,4]],"date-time":"2026-03-04T17:34:15Z","timestamp":1772645655193,"version":"3.50.1"},"reference-count":35,"publisher":"MDPI AG","issue":"10","license":[{"start":{"date-parts":[[2024,10,6]],"date-time":"2024-10-06T00:00:00Z","timestamp":1728172800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Entropy"],"abstract":"<jats:p>The domination problem and three of its variants (total domination, 2-domination, and secure domination) are considered. These problems have various real-world applications, including error correction codes, ad hoc routing for wireless networks, and social network analysis, among others. However, each of them is NP-hard to solve to provable optimality, making fast heuristics for these problems desirable. There are a wealth of highly developed heuristics and approximation algorithms for the domination problem; however, such heuristics are much less common for variants of the domination problem. We redress this gap in the literature by proposing a novel implementation of the cross-entropy method that can be applied to any sensible variant of domination. We present results from experiments that demonstrate that this approach can produce good results in an efficient manner even for larger graphs and that it works roughly as well for any of the domination variants considered.<\/jats:p>","DOI":"10.3390\/e26100844","type":"journal-article","created":{"date-parts":[[2024,10,7]],"date-time":"2024-10-07T08:35:23Z","timestamp":1728290123000},"page":"844","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["A Cross-Entropy Approach to the Domination Problem and Its Variants"],"prefix":"10.3390","volume":"26","author":[{"given":"Ryan","family":"Burdett","sequence":"first","affiliation":[{"name":"College of Science and Engineering, Flinders University, 1284 South Road, Tonsley Park, SA 5042, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8143-6583","authenticated-orcid":false,"given":"Michael","family":"Haythorpe","sequence":"additional","affiliation":[{"name":"College of Science and Engineering, Flinders University, 1284 South Road, Tonsley Park, SA 5042, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4401-0951","authenticated-orcid":false,"given":"Alex","family":"Newcombe","sequence":"additional","affiliation":[{"name":"College of Science and Engineering, Flinders University, 1284 South Road, Tonsley Park, SA 5042, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2024,10,6]]},"reference":[{"key":"ref_1","unstructured":"Garey, M.R., and Johnson, D.S. (1979). Computers and Intractability, Freeman."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"908","DOI":"10.1109\/TPDS.2004.48","article-title":"An extended localized algorithm for connected dominating set formation in ad hoc wireless networks","volume":"15","author":"Dai","year":"2004","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1016\/j.ins.2017.10.033","article-title":"An order-based algorithm for minimum dominating set with application in graph mining","volume":"426","author":"Chalupa","year":"2018","journal-title":"Inf. Sci."},{"key":"ref_4","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_5","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_6","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":"Mira","year":"2022","journal-title":"Theor. Comput. Sci."},{"key":"ref_7","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_8","unstructured":"Campan, A., Truta, T.M., and Beckerich, M. (2015, January 25\u201326). Fast Dominating Set Algorithms for Social Networks. Proceedings of the 26th Modern Artificial Intelligence and Cognitive Sciences Conference, Greensboro, NC, USA."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1016\/j.matcom.2022.12.018","article-title":"An iterated greedy algorithm for finding the minimum dominating set in graphs","volume":"207","author":"Casado","year":"2023","journal-title":"Math. Comput. Simul."},{"key":"ref_10","unstructured":"Eubank, S., Kumar, V.A., Marathe, M.V., Srinivasan, A., and Wang, N. (2004, January 11\u201313). 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_11","doi-asserted-by":"crossref","first-page":"89","DOI":"10.1016\/S0377-2217(96)00385-2","article-title":"Optimization of computer simulation models with rare events","volume":"99","author":"Rubinstein","year":"1997","journal-title":"Eur. J. Oper. Res."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1023\/A:1010091220143","article-title":"The cross-entropy method for combinatorial and continuous optimization","volume":"1","author":"Rubinstein","year":"1999","journal-title":"Methodol. Comput. Appl. Probab."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1007\/s10479-005-5724-z","article-title":"A tutorial on the cross-entropy method","volume":"134","author":"Kroese","year":"2005","journal-title":"Ann. Oper. Res."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1007\/s10479-009-0565-9","article-title":"A hybrid simulation-optimization algorithm for the Hamiltonian cycle problem","volume":"189","author":"Eshragh","year":"2011","journal-title":"Ann. Oper. Res."},{"key":"ref_15","unstructured":"Burger, A., De Villiers, A., and Van Vuuren, J. (2013, January 16\u201318). A binary programming approach towards achieving effective graph protection. Proceedings of the 2013 ORSSA Annual Conference, Stellenbosch, Western Cape, South Africa."},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Foerster, K.T. (2013, January 6). Approximating fault-tolerant domination in general graphs. Proceedings of the 2013 Tenth Workshop on Analytic Algorithmics and Combinatorics (ANALCO), New Orleans, LA, USA.","DOI":"10.1137\/1.9781611973037.4"},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"1264","DOI":"10.1016\/j.ic.2008.07.003","article-title":"Approximation hardness of dominating set problems in bounded degree graphs","volume":"206","year":"2008","journal-title":"Inf. Comput."},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Henning, M.A., and Yeo, A. (2013). Total Domination in Graphs, Springer Monographs in Mathematics, Springer.","DOI":"10.1007\/978-1-4614-6525-6"},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s00373-011-1040-3","article-title":"k-domination and k-independence in graphs: A survey","volume":"28","author":"Chellali","year":"2012","journal-title":"Graphs Comb."},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Klostermeyer, W.F., and Mynhardt, C.M. (2020). Eternal and Secure Domination in Graphs. Topics in Domination in Graphs, Developments in Mathematics, Springer.","DOI":"10.1007\/978-3-030-51117-3_13"},{"key":"ref_21","first-page":"321","article-title":"Two algorithms for secure graph domination","volume":"85","author":"Burger","year":"2013","journal-title":"J. Comb. Math. Comb. Comput."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"1443","DOI":"10.1137\/11082574","article-title":"The domination number of grids","volume":"25","author":"Pinlou","year":"2011","journal-title":"SIAM J. Discret. Math."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"561","DOI":"10.1007\/s10479-020-03810-6","article-title":"An improved binary programming formulation for the secure domination problem","volume":"295","author":"Burdett","year":"2020","journal-title":"Ann. Oper. Res."},{"key":"ref_24","first-page":"53114746","article-title":"The 2-domination and Roman domination numbers of grid graphs","volume":"21","author":"Rao","year":"2019","journal-title":"Discret. Math. Theor. Comput. Sci."},{"key":"ref_25","first-page":"319","article-title":"Results on total domination and total restrained domination in grid graphs","volume":"5","author":"Soltankhah","year":"2010","journal-title":"Int. Math. Forum"},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1080\/00029890.1975.11993805","article-title":"Infinite families of nontrivial trivalent graphs which are not Tait colorable","volume":"82","author":"Isaacs","year":"1975","journal-title":"Am. Math. Mon."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"P3.04","DOI":"10.26493\/1855-3974.2710.f3d","article-title":"Variants of the domination number for flower snarks","volume":"24","author":"Burdett","year":"2023","journal-title":"Ars Math. Contemp."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1016\/0012-365X(90)90358-O","article-title":"Unit disk graphs","volume":"86","author":"Clark","year":"1990","journal-title":"Discret. Math."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"036104","DOI":"10.1103\/PhysRevE.74.036104","article-title":"Finding community structure in networks using the eigenvectors of matrices","volume":"74","author":"Newman","year":"2006","journal-title":"Phys. Rev. E"},{"key":"ref_30","doi-asserted-by":"crossref","unstructured":"Johnson, D.S., and Trick, M.A. (1996). Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge, October 11\u201313, 1993, American Mathematical Society.","DOI":"10.1090\/dimacs\/026"},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"396","DOI":"10.1007\/s00265-003-0651-y","article-title":"The bottlenose dolphin community of doubtful sound features a large proportion of long-lasting associations: Can geographic isolation explain this unique trait?","volume":"54","author":"Lusseau","year":"2003","journal-title":"Behav. Ecol. Sociobiol."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"7821","DOI":"10.1073\/pnas.122653799","article-title":"Community structure in social and biological networks","volume":"99","author":"Girvan","year":"2002","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"ref_33","unstructured":"Knuth, D.E. (1993). The Stanford GraphBase: A Platform for Combinatorial Computing, ACM Press."},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"440","DOI":"10.1038\/30918","article-title":"Collective dynamics of \u2018small-world\u2019networks","volume":"393","author":"Watts","year":"1998","journal-title":"Nature"},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"452","DOI":"10.1086\/jar.33.4.3629752","article-title":"An information flow model for conflict and fission in small groups","volume":"33","author":"Zachary","year":"1977","journal-title":"J. Anthropol. Res."}],"container-title":["Entropy"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1099-4300\/26\/10\/844\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T16:11:48Z","timestamp":1760112708000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1099-4300\/26\/10\/844"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,10,6]]},"references-count":35,"journal-issue":{"issue":"10","published-online":{"date-parts":[[2024,10]]}},"alternative-id":["e26100844"],"URL":"https:\/\/doi.org\/10.3390\/e26100844","relation":{},"ISSN":["1099-4300"],"issn-type":[{"value":"1099-4300","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,10,6]]}}}