
Upper Domination: Towards a Dichotomy Through Boundary Properties
AbouEisha, Hassan; Hussain, Shahid; Lozin, Vadim; Monnot, Jérôme; Ries, Bernard; Zamaraev, Viktor (2018), Upper Domination: Towards a Dichotomy Through Boundary Properties, Algorithmica, 80, 10, p. 2799-2817. 10.1007/s00453-017-0346-9
View/ Open
Type
Article accepté pour publication ou publiéDate
2018Journal name
AlgorithmicaVolume
80Number
10Publisher
Springer
Pages
2799-2817
Publication identifier
Metadata
Show full item recordAuthor(s)
AbouEisha, HassanCenter for Numerical Porous Media (NumPor) - King Abdullah University of Science and Technology
Hussain, Shahid
autre
Lozin, Vadim
Warwick Mathematics Institute [WMI]
Monnot, Jérôme

Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Ries, Bernard
Zamaraev, Viktor
Warwick Mathematics Institute [WMI]
Abstract (EN)
An upper 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 boundary classes. However, none of such classes has been identified so far for the upper dominating set problem. We discover the first boundary class for this problem and prove the dichotomy for monogenic classes.Subjects / Keywords
Upper dominating set; Boundary class; Complexity dichotomy; NP-hardRelated items
Showing items related by title and author.
-
AbouEisha, Hassan; Hussain, Shahid; Lozin, Vadim; Monnot, Jérôme; Ries, Bernard (2014) Communication / Conférence
-
AbouEisha, Hassan; Hussain, Shahid; Lozin, Vadim; Monnot, Jérôme; Ries, Bernard; Zamaraev, Viktor (2016) Communication / Conférence
-
Ries, Bernard; Monnot, Jérôme; Lozin, Vadim (2015) Article accepté pour publication ou publié
-
Lozin, Vadim; Monnot, Jérôme; Ries, Bernard (2013) Communication / Conférence
-
Ries, Bernard; Raman, Rajiv; Lozin, Vadim; Dabrowski, Konrad Kazimierz (2012) Article accepté pour publication ou publié