An improved binary programming formulation for the secure domination problem

DOI10.1007/S10479-020-03810-6MaRDI QIDQ828823zbMATH OpenOpenAlexFDO

Authors Ryan Burdett, Michael Haythorpe

Publication date 5 May 2021

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

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)

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.

Recommendations

• On secure domination in graphs
• Two algorithms for secure graph domination
• Improved mixed integer linear programing formulations for Roman domination problem
• The complexity of secure domination problem in graphs
• On computing secure domination of trees

Cites work

• scientific article; zbMATH DE number 3702724 (Why is no real title available?)
• scientific article; zbMATH DE number 2188604 (Why is no real title available?)
• A linear algorithm for secure domination in trees
• A theorem on tait colorings with an application to the generalized Petersen graphs
• Complexity issues of variants of secure domination in graphs
• Exact algorithms for dominating set
• Integer Programming Formulation of Traveling Salesman Problems
• On computing a minimum secure dominating set in block graphs
• On secure domination in graphs
• On the secure domination numbers of maximal outerplanar graphs
• Optimization of wireless sensor networks deployment with coverage and connectivity constraints
• Solving the connected dominating set problem and power dominating set problem by integer programming
• The complexity of secure domination problem in graphs
• Two algorithms for secure graph domination

Cited in

(8)

• Correcting the algorithm for the secure domination number of cographs by Jha, Pradhan, and Banerjee
• Linear programming formulation for some generalized domination parameters
• PTASs for secure dominating set in planar graphs and growth-bounded graphs
• A compact mixed integer linear formulation for safe set problems
• Improved mixed integer linear programing formulations for Roman domination problem
• Variants of the domination number for flower snarks
• The secure domination number of Cartesian products of small graphs with paths and cycles
• Binary programming formulations for the upper domination problem

Describes a project that uses

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)