×

Improved integer linear programming formulation for weak Roman domination problem. (English) Zbl 1402.90197

Summary: Let \(f:V \to\{0,1,2\}\) be a function, \(G=(V,E)\) be a graph with a vertex set \(V\) and a set of edges \(E\) and let the weight of the vertex \(u \in V\) be defined by \(f(u)\). A vertex \(u\) with property \(f(u)=0\) is considered to be defended with respect to the function \(f\) if it is adjacent to a vertex with positive weight. Further, the function \(f\) is called a weak Roman dominating function (WRDF) if, for every vertex \(u\) with property \(f(u)=0\), there exists at least one adjacent vertex \(v\) with positive weight such that the function \(f':V \to\{0,1,2\}\) defined by \(f'(u)=1\), \(f'(v)=f(v)-1\) and \(f'(w)=f(w)\), \(w \in V \setminus\{u,v\}\) has no undefended vertices. In this paper, an optimization problem of finding the WRDF \(f\) such that \(\sum _{u \in V}f(u)\) is minimal, known as the weak Roman domination problem (WRDP), is considered. Therefore, a new integer linear programing (ILP) formulation is proposed and compared with the one known from the literature. Comparison between the new and the existing formulation is made through computational experiments on a grid, planar, net and randomly generated graphs known from the literature and up to 600 vertices. Tests were run using standard CPLEX and Gurobi optimization solvers. The obtained results demonstrate that the proposed new ILP formulation clearly outperforms the existing formulation in the sense of solutions’ quality and running times.

MSC:

90C35 Programming involving graphs or networks
05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
90C05 Linear programming
90C10 Integer programming

Software:

Gurobi; CPLEX
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ahangar, HA; Henning, MA; Löwenstein, C.; Zhao, Y.; Samodivkin, V., Signed Roman domination in graphs, J Comb Optim, 27, 241-255, (2014) · Zbl 1319.90070 · doi:10.1007/s10878-012-9500-0
[2] Alvarado JD, Dantas S, Rautenbach D (2015a) Relating \(2\)-rainbow domination to weak roman domination. arXiv preprint arXiv:1512.01067 · Zbl 1375.05188
[3] Alvarado JD, Dantas S, Rautenbach D (2015b) Strong Equality of Roman and Weak Roman Domination in Trees. arXiv preprint arXiv:1507.04901 · Zbl 1336.05098
[4] Alvarez-Ruiz M, Yero IG, Mediavilla-Gradolph T, Valenzuela J (2015) A stronger vision for roman domination in graphs. arXiv preprint arXiv:1502.03933
[5] Burger A, De Villiers A, Van Vuuren J (2013) A binary programming approach towards achieving effective graph protection. In: Proceedings of the 2013 ORSSA annual conference, ORSSA, 2013, pp 19-30
[6] Chang GJ, Chen SH, Liu CH (2014) Edge roman domination on graphs. arXiv preprint arXiv:1405.5622
[7] Chapelle M, Cochefert M, Couturier JF, Kratsch D, Liedloff M, Perez A (2013) Exact algorithms for weak roman domination. In: Combinatorial Algorithms, Springer, pp 81-93 · Zbl 1408.68112
[8] Chellali, M.; Haynes, TW; Hedetniemi, ST, Bounds on weak Roman and 2-rainbow domination numbers, Discrete Appl Math, 178, 27-32, (2014) · Zbl 1300.05212 · doi:10.1016/j.dam.2014.06.016
[9] Cockayne, E.; Grobler, P.; Grundlingh, W.; Munganga, J.; Jv, Vuuren, Protection of a graph, Util Math, 67, 19-32, (2005) · Zbl 1081.05083
[10] Currò V (2014) The roman domination problem on grid graphs. Ph.D. thesis, Università di Catania
[11] Dreyer PA Jr (2000) Applications and variations of domination in graphs. Ph.D. thesis, Citeseer
[12] Henning, MA, Defending the Roman empire from multiple attacks, Discret Math, 271, 101-115, (2003) · Zbl 1022.05055 · doi:10.1016/S0012-365X(03)00040-2
[13] Henning, MA; Hedetniemi, ST, Defending the Roman empire a new strategy, Discret Math, 266, 239-251, (2003) · Zbl 1024.05068 · doi:10.1016/S0012-365X(02)00811-7
[14] Klobučar, A.; Puljić, I., Some results for Roman domination number on cardinal product of paths and cycles, Kragujev J Math, 38, 83-94, (2014) · Zbl 1464.05292 · doi:10.5937/KgJMath1401083K
[15] Lai YL, Lin CT, Ho HM (2011) Weak roman domination on graphs. In: Proceedings of the 28th workshop on combinatorial mathematics and computation theory, Penghu University of Science and Technology, Penghu, Taiwan, May 27-28, 2011, pp 224-214
[16] Liedloff M, Kloks T, Liu J, Peng SL (2005) Roman domination over some graph classes. In: Graph-Theoretic Concepts in Computer Science, Springer, pp 103-114 · Zbl 1171.05389
[17] Liu CS, Peng SL, Tang CY (2010) Weak Roman Domination on Block Graphs. In: Proceedings of The 27th workshop on combinatorial mathematics and computation theory, Providence University, Taichung, Taiwan, April 30-May 1, 2010, pp 86-89
[18] Pushpam, PRL; Kamalam, M., Efficient weak Roman domination in myscielski graphs, Int J Pure Eng Math (IJPEM), 3, 93-100, (2015)
[19] Pushpam, PRL; Kamalam, M., Efficient weak Roman domination in graphs, Int J Pure Appl Math, 101, 701-710, (2015)
[20] Pushpam, PRL; Mai, TM, Weak Roman domination in graphs, Discuss Math Graph Theory, 31, 161-170, (2011) · Zbl 1284.05201 · doi:10.7151/dmgt.1535
[21] ReVelle CS, Rosing KE (2000) Defendens imperium romanum: a classical problem in military strategy. Am Math Mon 107(7):585-594 · Zbl 1039.90038
[22] Shang W, Hu X (2007) The roman domination problem in unit disk graphs. In: Computational Science-ICCS 2007, Springer, pp 305-312
[23] Song X, Yang J, Xie Y (2011) Weak Roman domination in 2xn grid graphs. J Henan Univ (Nat Sci) 41(1): 4-9 (in Chinese)
[24] Song, X.; Bian, J.; Yin, W., Six safe grades on weak Roman domination, J Henan Univ (Nat Sci), 5, 002, (2013) · Zbl 1330.05119
[25] Stewart, I., Defend the Roman empire!, Sci Am, 281, 136-138, (1999) · doi:10.1038/scientificamerican1299-136
[26] Targhi, M.; Rad, NJ; Moradi, MS, Properties of independent Roman domination in graphs, Australas J Combin, 52, 11-18, (2012) · Zbl 1251.05116
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.