An improved binary programming formulation for the secure domination problem

DOI10.1007/S10479-020-03810-6zbMATH Open1462.05273arXiv1911.02198OpenAlexW3088670687MaRDI QIDQ828823FDOQ828823

Ryan Burdett, Michael Haythorpe

Publication date: 5 May 2021

Published in: Annals of Operations Research (Search for Journal in Brave)

Abstract: 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.

Full work available at URL: https://arxiv.org/abs/1911.02198

zbMATH Keywords

formulationsecure dominationbinary programmingsecure connected

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Integer Programming Formulation of Traveling Salesman Problems
• A theorem on tait colorings with an application to the generalized Petersen graphs
• Solving the Connected Dominating Set Problem and Power Dominating Set Problem by Integer Programming
• On secure domination in graphs
• Exact algorithms for dominating set
• A linear algorithm for secure domination in trees
• Optimization of wireless sensor networks deployment with coverage and connectivity constraints
• On the secure domination numbers of maximal outerplanar graphs
• On computing a minimum secure dominating set in block graphs
• The complexity of secure domination problem in graphs
• Complexity issues of variants of secure domination in graphs

Cited In (5)

• Correcting the algorithm for the secure domination number of cographs by Jha, Pradhan, and Banerjee
• Variants of the domination number for flower snarks
• PTASs for secure dominating set in planar graphs and growth-bounded graphs
• Binary programming formulations for the upper domination problem
• The secure domination number of Cartesian products of small graphs with paths and cycles

Uses Software

• CPLEX

This page was built for publication: An improved binary programming formulation for the secure domination problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q828823)