Thumbnail

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, dans 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

Voir/Ouvrir
Type
Communication / Conférence
Date
2014
Titre du colloque
8th International Conference, COCOA 2014
Date du colloque
2014-12
Ville du colloque
Wailea, Maui, HI
Pays du colloque
United States
Titre de l'ouvrage
Combinatorial Optimization and Applications
Auteurs de l’ouvrage
Zhang, Zhao; Wu, Lidong; Xu, Wen; Du, Ding-Zhu
Éditeur
Springer International Publishing
Ville d’édition
Cham
Isbn
978-3-319-12690-6
Nombre de pages
774
Pages
258-267
Identifiant publication
Métadonnées
Afficher la notice complète
Auteur(s)
AbouEisha, Hassan
Center 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 cc
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]
Résumé (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.
Mots-clés
graphs
JEL
C44 - Operations Research; Statistical Decision Theory