{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:24:19Z","timestamp":1740108259365,"version":"3.37.3"},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2023,7,20]],"date-time":"2023-07-20T00:00:00Z","timestamp":1689811200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,7,20]],"date-time":"2023-07-20T00:00:00Z","timestamp":1689811200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001785","name":"Flinders University","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100001785","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math Meth Oper Res"],"published-print":{"date-parts":[[2023,10]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We consider Upper Domination, the problem of finding the minimal dominating set of maximum cardinality. Very few exact algorithms have been described for solving Upper Domination. In particular, no binary programming formulations for Upper Domination have been described in literature, although such formulations have proved quite successful for other kinds of domination problems. We introduce two such binary programming formulations, and show that both can be improved with the addition of extra constraints which reduce the number of feasible solutions. We compare the performance of the formulations on various kinds of graphs, and demonstrate that (a) the additional constraints improve the performance of both formulations, and (b) the first formulation outperforms the second in most cases, although the second performs better for very sparse graphs. Also included is a short proof that the upper domination number of any generalized Petersen graph <jats:italic>P<\/jats:italic>(<jats:italic>n<\/jats:italic>,\u00a0<jats:italic>k<\/jats:italic>) is equal to <jats:italic>n<\/jats:italic>.<\/jats:p>","DOI":"10.1007\/s00186-023-00831-2","type":"journal-article","created":{"date-parts":[[2023,7,20]],"date-time":"2023-07-20T04:05:02Z","timestamp":1689825902000},"page":"155-168","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Binary programming formulations for the upper domination problem"],"prefix":"10.1007","volume":"98","author":[{"given":"Ryan","family":"Burdett","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8143-6583","authenticated-orcid":false,"given":"Michael","family":"Haythorpe","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4401-0951","authenticated-orcid":false,"given":"Alex","family":"Newcombe","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,7,20]]},"reference":[{"issue":"1","key":"831_CR1","doi-asserted-by":"publisher","first-page":"P141","DOI":"10.37236\/628","volume":"18","author":"S Alanko","year":"2011","unstructured":"Alanko S, Crevals S, Isopoussu A, \u00d6sterg\u00e5rd P, Pettersson V (2011) Computing the domination number of grid graphs. Electron. J. Comb. 18(1):P141","journal-title":"Electron. J. Comb."},{"key":"831_CR2","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1016\/j.tcs.2017.05.042","volume":"717","author":"C Bazgan","year":"2018","unstructured":"Bazgan C, Brankovic L, Casel K, Fernau H, Jansen K, Klein KM, Lampis M, Liedloff M, Monnot J, Paschos VT (2018) The many facets of upper domination. Theoret. Comput. Sci. 717:2\u201325","journal-title":"Theoret. Comput. Sci."},{"issue":"9","key":"831_CR3","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2021.112495","volume":"344","author":"A Burcroff","year":"2021","unstructured":"Burcroff A (2021) Tightness of domination inequalities for direct product graphs. Discret. Math. 344(9):112495","journal-title":"Discret. Math."},{"key":"831_CR4","doi-asserted-by":"publisher","first-page":"561","DOI":"10.1007\/s10479-020-03810-6","volume":"295","author":"R Burdett","year":"2020","unstructured":"Burdett R, Haythorpe M (2020) An improved binary programming formulation for the secure domination problem. Ann. Oper. Res. 295:561\u2013573","journal-title":"Ann. Oper. Res."},{"key":"831_CR5","unstructured":"Burdett R, Haythorpe M, Newcombe A (2021) Variants of the domination number for flower snarks, Arxiv preprint, arXiv:2110.01838"},{"key":"831_CR6","unstructured":"Burger, A.P., De Villiers, A.P., Van Vuuren, J.H.: A binary programming approach towards achieving effective graph protection. In: Proc. 2013 ORSSA Annual Conf., ORRSA, pp. 19\u201330 (2013)"},{"key":"831_CR7","first-page":"321","volume":"85","author":"AP Burger","year":"2013","unstructured":"Burger AP, De Villiers AP, Van Vuuren JH (2013) Two algorithms for secure graph domination. J. Comb. Math. Comb. Comput. 85:321\u2013339","journal-title":"J. Comb. Math. Comb. Comput."},{"issue":"1\u20133","key":"831_CR8","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1016\/0012-365X(90)90358-O","volume":"86","author":"BN Clark","year":"1990","unstructured":"Clark BN, Colbourn CJ, Johnson DS (1990) Unit disk graphs. Discret. Math. 86(1\u20133):165\u2013177","journal-title":"Discret. Math."},{"issue":"3","key":"831_CR9","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1016\/0012-365X(81)90268-5","volume":"33","author":"EJ Cockayne","year":"1981","unstructured":"Cockayne EJ, Favaron O, Payan C, Thomason AG (1981) Contributions to the theory of domination, independence and irredundance in graphs. Discret. Math. 33(3):249\u2013258","journal-title":"Discret. Math."},{"issue":"5","key":"831_CR10","doi-asserted-by":"publisher","first-page":"413","DOI":"10.1090\/S0002-9904-1950-09407-5","volume":"56","author":"HSM Coxeter","year":"1950","unstructured":"Coxeter HSM (1950) Self-dual configurations and regular graphs. Bull. Am. Math. Soc. 56(5):413\u2013455","journal-title":"Bull. Am. Math. Soc."},{"issue":"6","key":"831_CR11","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 MA (2006) A note on power domination in grid graphs. Discret. Appl. Math. 154(6):1023\u20131027","journal-title":"Discret. Appl. Math."},{"key":"831_CR12","doi-asserted-by":"publisher","first-page":"371","DOI":"10.1007\/978-3-642-31770-5_33","volume-title":"International Conference on Combinatorial Optimization and Applications","author":"N Fan","year":"2012","unstructured":"Fan N, Watson JP (2012) Solving the connected dominating set problem and power dominating set problem by integer programming. International Conference on Combinatorial Optimization and Applications. Springer, Berlin, Heidelberg, pp 371\u2013383"},{"issue":"1","key":"831_CR13","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1435375.1435384","volume":"5","author":"FV Fomin","year":"2008","unstructured":"Fomin FV, Grandoni F, Pyatkin AV, Stepanov AA (2008) Combinatorial bounds via measure and conquer: bounding minimal dominating sets and applications. ACM Trans. Algorithms 5(1):1\u201317","journal-title":"ACM Trans. Algorithms"},{"key":"831_CR14","unstructured":"Fricke, G.H., Hedetniemi, S.M., Hedetniemi, S.T., McRae, A.A., Wallis, C.K., Jacobson, M.S., Martin, H.W., Weakley, W.D.: Combinatorial problems on chessboards: a brief survey. In: Graph Theory, Combinatorics, and Algorithms: Proc. 7th Quadrennial International Conference on the Theory and Applications of Graphs (Y. Alavi and A. Schwenk, eds.) Vol. 1, pp. 507\u2013528 (1995)"},{"issue":"3","key":"831_CR15","doi-asserted-by":"publisher","first-page":"1443","DOI":"10.1137\/11082574","volume":"25","author":"D Gon\u00e7alves","year":"2011","unstructured":"Gon\u00e7alves D, Pinlou A, Rao M, Thomass\u00e9 S (2011) The domination number of grids. SIAM J. Discret. Math. 25(3):1443\u20131453","journal-title":"SIAM J. Discret. Math."},{"issue":"1\u20133","key":"831_CR16","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1016\/S0166-218X(01)00297-9","volume":"121","author":"S Gravier","year":"2002","unstructured":"Gravier S (2002) Total domination number of grid graphs. Discret. Appl. Math. 121(1\u20133):119\u2013128","journal-title":"Discret. Appl. Math."},{"key":"831_CR17","doi-asserted-by":"crossref","unstructured":"Hedetniemi, J.T., Hedetniemi, S.T.: Domination in Chessboards. Structures of Domination in Graphs, Springer, pp. 341\u2013386. (2021)","DOI":"10.1007\/978-3-030-58892-2_12"},{"issue":"113","key":"831_CR18","first-page":"51","volume":"99","author":"M Ivanovi\u0107","year":"2016","unstructured":"Ivanovi\u0107 M (2016) Improved mixed integetr linear programming formulations for Roman domination problem. Publ. de L\u2019Institut Math\u00e9matique 99(113):51\u201358","journal-title":"Publ. de L\u2019Institut Math\u00e9matique"},{"issue":"19","key":"831_CR19","doi-asserted-by":"publisher","first-page":"6583","DOI":"10.1007\/s00500-017-2706-4","volume":"22","author":"M Ivanovi\u0107","year":"2018","unstructured":"Ivanovi\u0107 M (2018) Improved integer linear programming formulation for weak Roman domination problem. Soft. Comput. 22(19):6583\u20136593","journal-title":"Soft. Comput."},{"issue":"2","key":"831_CR20","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1002\/net.3230250205","volume":"25","author":"MV Marathe","year":"1995","unstructured":"Marathe MV, Breu H, Hunt HB III, Ravi SS, Rosenkratz DJ (1995) Simple heuristics for unit disk graphs. Networks 25(2):59\u201368","journal-title":"Networks"},{"issue":"7","key":"831_CR21","doi-asserted-by":"publisher","first-page":"585","DOI":"10.1080\/00029890.2000.12005243","volume":"107","author":"CS ReVelle","year":"2000","unstructured":"ReVelle CS, Rosing KE (2000) Defendens imperium romanum: a callsical problem in military strategy. Am. Math. Mon. 107(7):585\u2013594","journal-title":"Am. Math. Mon."},{"issue":"4","key":"831_CR22","doi-asserted-by":"publisher","first-page":"262","DOI":"10.1007\/BF02759743","volume":"2","author":"M Rosenfeld","year":"1964","unstructured":"Rosenfeld M (1964) Independent sets in regular graphs. Israel J. Math. 2(4):262\u2013272","journal-title":"Israel J. Math."},{"issue":"01","key":"831_CR23","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1142\/S1793830910000504","volume":"2","author":"W Shang","year":"2010","unstructured":"Shang W, Wang X, Hu X (2010) Roman domination and its variants in unit disk graphs. Discrete Math. Algorithms Appl. 2(01):99\u2013105","journal-title":"Discrete Math. Algorithms Appl."},{"key":"831_CR24","doi-asserted-by":"crossref","unstructured":"Simonetti, L., Salles de Cunha, A., Lucena, A.: The Minimum Connected Dominating Set Problems: Formulation, Valid Inequalities and a Branch-and-Cut Algorithm. In: Pahl J., Reiners T., Vo\u00df S. (eds) Network Optimization. INOC 2011. Lecture Notes in Computer Science, (vol. 6701. Springer, Belin, Heidelberg), pp. 162\u2013169. (2011)","DOI":"10.1007\/978-3-642-21527-8_21"},{"key":"831_CR25","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2023.113824","volume":"957","author":"CX Wang","year":"2023","unstructured":"Wang CX, Yang Y, Xu SJ (2023) Secure connected domination and secure total domination in unit disk graphs and rectangle graphs. Theor. Comput. Sci. 957:113824","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"831_CR26","doi-asserted-by":"publisher","first-page":"152","DOI":"10.1016\/S0021-9800(69)80116-X","volume":"6","author":"ME Watkins","year":"1969","unstructured":"Watkins ME (1969) A theorem on Tait colorings with an application to the generalized Petersen graphs. J. Comb. Theory 6(2):152\u2013164","journal-title":"J. Comb. Theory"}],"container-title":["Mathematical Methods of Operations Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00186-023-00831-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00186-023-00831-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00186-023-00831-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,16]],"date-time":"2023-10-16T13:05:08Z","timestamp":1697461508000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00186-023-00831-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,7,20]]},"references-count":26,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2023,10]]}},"alternative-id":["831"],"URL":"https:\/\/doi.org\/10.1007\/s00186-023-00831-2","relation":{},"ISSN":["1432-2994","1432-5217"],"issn-type":[{"type":"print","value":"1432-2994"},{"type":"electronic","value":"1432-5217"}],"subject":[],"published":{"date-parts":[[2023,7,20]]},"assertion":[{"value":"2 March 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 July 2023","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 July 2023","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 July 2023","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 have no relevant financial or non-financial interests to disclose.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}