
A Dichotomy for Upper Domination in Monogenic Classes
AbouEisha, Hassan; Hussain, Shahid; Lozin, Vadim; Monnot, Jérôme; Ries, Bernard (2014), A Dichotomy for Upper Domination in Monogenic Classes, in Zhang, Zhao; Wu, Lidong; Xu, Wen; Du, Ding-Zhu, Combinatorial Optimization and Applications, Springer International Publishing : Cham, p. 258-267. 10.1007/978-3-319-12691-3_20
View/ Open
Type
Communication / ConférenceDate
2014Conference title
8th International Conference, COCOA 2014Conference date
2014-12Conference city
Wailea, Maui, HIConference country
United StatesBook title
Combinatorial Optimization and ApplicationsBook author
Zhang, Zhao; Wu, Lidong; Xu, Wen; Du, Ding-ZhuPublisher
Springer International Publishing
Published in
Cham
ISBN
978-3-319-12690-6
Number of pages
774Pages
258-267
Publication identifier
Metadata
Show full item recordAuthor(s)
AbouEisha, HassanCenter for Numerical Porous Media (NumPor) - King Abdullah University of Science and Technology
Hussain, Shahid
Center for Numerical Porous Media (NumPor) - King Abdullah University of Science and Technology
Lozin, Vadim
Centre for Discrete Mathematics and its Applications [Warwick] [DIMAP]
Monnot, Jérôme

Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Ries, Bernard
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Abstract (EN)
An upper dominating set in a graph is a minimal (with respect to set inclusion) dominating set of maximum cardinality. The problem of finding an upper dominating set is NP-hard for general graphs and in many restricted graph families. In the present paper, we study the computational complexity of this problem in monogenic classes of graphs (i.e. classes defined by a single forbidden induced subgraph) and show that the problem admits a dichotomy in this family. In particular, we prove that if the only forbidden induced subgraph is a P4 or a 2K2 (or any induced subgraph of these graphs), then the problem can be solved in polynomial time. Otherwise, it is NP-hard.Subjects / Keywords
graphsRelated items
Showing items related by title and author.
-
AbouEisha, Hassan; Hussain, Shahid; Lozin, Vadim; Monnot, Jérôme; Ries, Bernard; Zamaraev, Viktor (2018) Article accepté pour publication ou publié
-
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; Pop, Petrica; Monnot, Jérôme; Demange, Marc (2012) Communication / Conférence