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 language | English |
---|---|
Pages (from-to) | 155-168 |
Number of pages | 14 |
Journal | Mathematical Methods of Operations Research |
Volume | 98 |
Issue number | 2 |
Early online date | 20 Jul 2023 |
DOIs | |
Publication status | Published - Oct 2023 |
Keywords
- Binary programming
- Formulation
- Graphs
- Minimal dominating set
- Upper domination