Affiner les résultats

Upper Domination : Towards a Dichotomy Through Boundary Properties

AbouEisha, Hassan ; Shahid, Hussain ; Lozin, Vadim ; Monnot, Jérôme ; Ries, Bernard ; Zamaraev, Viktor

In: Algorithmica, 2018, vol. 80, no. 10, p. 2799-2817

Anupper dominating set in a graph is a minimal dominating set of maximum cardinality. The problem of finding an upper dominating set is generally NP-hard.We study the complexity of this problem in finitely defined classes of graphs and conjecture that the problem admits a complexity dichotomy in this family. A helpful tool to study the complexity of an algorithmic problem is the notion of...