An improved binary programming formulation for the secure domination problem. (English) Zbl 1462.05273
Summary: The secure domination problem, a variation of the domination problem with some important real-world applications, is considered. Very few algorithmic attempts to solve this problem have been presented in literature, and the most successful to date is a binary programming formulation which is solved using CPLEX. A new binary programming formulation is proposed here which requires fewer constraints and fewer binary variables than the existing formulation. It is implemented in CPLEX, and tested on certain families of graphs that have previously been considered in the context of secure domination. It is shown that the runtime required for the new formulation to solve the instances is significantly less than that of the existing formulation. An extension of our formulation that solves the related, but further constrained, secure connected domination problem is also given; to the best of the authors’ knowledge, this is the first such formulation in literature.
MSC:
| 05C69 | Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) |
Software:
CPLEXReferences:
| [1] | Araki, T.; Yumoto, I., On the secure domination numbers of maximal outerplanar graphs, Discrete Applied Mathematics, 236, 23-29 (2018) · Zbl 1377.05135 · doi:10.1016/j.dam.2017.10.020 |
| [2] | Burger, AP; de Villiers, AP; van Vuuren, JH, Two algorithms for secure graph domination, Journal of Combinatorial Mathematics and Combinatorial Computing, 85, 321-339 (2013) · Zbl 1274.05349 |
| [3] | Burger, A.P., de Villiers, A.P., & van Vuuren, J.H. (2013). A binary programming approach towards achieving effective graph protection. In: Proceedings of the 2013 ORSSA annual conference, ORSSA 2013, pp. 19-30. |
| [4] | Burger, AP; de Villiers, AP; van Vuuren, JH, A linear algorithm for secure domination in trees, Discrete Applied Mathematics, 171, 15-27 (2014) · Zbl 1288.05189 · doi:10.1016/j.dam.2014.02.001 |
| [5] | Cabaro, AG; Canoy, SR Jr, Secure connected dominating sets in the join and composition of graphs, International Journal of Mathematical Analysis, 9, 25, 1241-1248 (2015) · doi:10.12988/ijma.2015.5247 |
| [6] | Cockayne, EJ; Grobler, PJP; Grundlingh, WR; Munganga, J.; van Vuuren, JH, Protection of a graph, Utilitas Mathematica, 67, 19-32 (2005) · Zbl 1081.05083 |
| [7] | Elloumi, S.; Hudry, O.; Marie, E.; Martin, A.; Plateau, A.; Rovedakis, S., Optimization of wireless sensor networks deployment with coverage and connectivity constraints, Annals of Operations Research (2018) · Zbl 1511.68034 · doi:10.1007/s10479-018-2943-7 |
| [8] | De Jaenisch, C.F. (1862). Traité des applications de l’analyse mathématique au jeu des échecs. L’Académie Impériale Des Sciences. |
| [9] | Fan, N., Watson, J.P. (2012). Solving the connected dominating set problem and power dominating set problem by integer programming. In: G. Lin (Ed.) Combinatorial optimization and applications. Lecture notes in computer sciences (Vol. 7402, pp. 371-383), Berlin/Heidelberg, Springer. · Zbl 1358.05214 |
| [10] | Haynes, TW; Hedetniemi, S.; Slater, P., Fundamentals of domination in graphs (2013), Boca Raton: CRC Press, Boca Raton · doi:10.1201/9781482246582 |
| [11] | Lad, D.; Reddy, PVS; Kumar, JP, Complexity issues of variants of secure domination in graphs, Electronic Notes in Discrete Mathematics, 63, 77-84 (2017) · Zbl 1383.05241 · doi:10.1016/j.endm.2017.11.001 |
| [12] | Merouane, HB; Chellali, M., On secure domination in graphs, Information Processing Letters, 115, 15, 786-790 (2015) · Zbl 1329.05223 · doi:10.1016/j.ipl.2015.05.006 |
| [13] | Miller, CE; Tucker, AW; Zemlin, RA, Integer programming formulation of traveling salesman problems, Journal of ACM, 7, 4, 326-329 (1960) · Zbl 0100.15101 · doi:10.1145/321043.321046 |
| [14] | Pradhan, D.; Jha, A., On computing a minimum secure dominating set in block graphs, Journal of Combinatorial Optimization, 35, 2, 613-631 (2018) · Zbl 1386.05143 · doi:10.1007/s10878-017-0197-y |
| [15] | Sampathkumar, E.; Walikar, HB, The connected domination number of a graph, Journal of Mathematical and Physical Sciences, 13, 6, 607-613 (1979) · Zbl 0449.05057 |
| [16] | Van Rooji, JMM; Bodlaender, HL, Exact algorithms for dominating set, Discrete Applied Mathematics, 159, 17, 2147-2164 (2011) · Zbl 1237.05157 · doi:10.1016/j.dam.2011.07.001 |
| [17] | Wang, H.; Zhao, Y.; Deng, Y., The complexity of secure domination problem in graphs, Discussiones Mathematicae Graph Theory, 38, 2, 385-398 (2018) · Zbl 1390.05182 · doi:10.7151/dmgt.2008 |
| [18] | Watkins, ME, A theorem on tait colorings with an application to the generalized petersen graphs, Journal of Combinatorial Theory, 6, 152-164 (1969) · Zbl 0175.50303 · doi:10.1016/S0021-9800(69)80116-X |
| [19] | Winter, A. (2018). Domination, Total Domination and Secure Domination. Honours Thesis, University of South Australia. |
| [20] | Yuan, D. (2005). Energy-efficient broadcastig in wireless ad hoc networks: Performance benchmarking and distributed algorithms based on network connectivity characterization. In Proceedings of the 8th ACM international symposium on modeling, analysis and simulation of wireless and mobile systems, pp. 28-35. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
