An improved binary programming formulation for the secure domination problem

Ryan Burdett () and Michael Haythorpe ()
Additional contact information
Ryan Burdett: Flinders University
Michael Haythorpe: Flinders University

Annals of Operations Research, 2020, vol. 295, issue 2, No 3, 573 pages

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

Keywords: Secure; Domination; Graph; Binary programming; Formulation; Secure connected (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10479-020-03810-6 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:295:y:2020:i:2:d:10.1007_s10479-020-03810-6

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-020-03810-6

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().