Binary programming formulations for the upper domination problem

Research output: Contribution to journalArticlepeer-review

44 Downloads (Pure)

Abstract

We consider Upper Domination, the problem of finding the minimal dominating set of maximum cardinality. Very few exact algorithms have been described for solving Upper Domination. In particular, no binary programming formulations for Upper Domination have been described in literature, although such formulations have proved quite successful for other kinds of domination problems. We introduce two such binary programming formulations, and show that both can be improved with the addition of extra constraints which reduce the number of feasible solutions. We compare the performance of the formulations on various kinds of graphs, and demonstrate that (a) the additional constraints improve the performance of both formulations, and (b) the first formulation outperforms the second in most cases, although the second performs better for very sparse graphs. Also included is a short proof that the upper domination number of any generalized Petersen graph P(n, k) is equal to n.

Original languageEnglish
Pages (from-to)155-168
Number of pages14
JournalMathematical Methods of Operations Research
Volume98
Issue number2
Early online date20 Jul 2023
DOIs
Publication statusPublished - Oct 2023

Keywords

  • Binary programming
  • Formulation
  • Graphs
  • Minimal dominating set
  • Upper domination

Fingerprint

Dive into the research topics of 'Binary programming formulations for the upper domination problem'. Together they form a unique fingerprint.

Cite this