A Dichotomy for Upper Domination in Monogenic Classes
Overview & Synopsis
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.
Indexed from repository: HAL Open Science
(
hal.science)
Keyboard Shortcuts:
← / → for pages • + / - for zoom • 0 to fit width
Powered by Mozilla PDF.js v3.11
Document Information
| Document Title | A Dichotomy for Upper Domination in Monogenic Classes |
|---|---|
| Author / Organization | Hassan Aboueisha, Shahid Hussain, Vadim Lozin, Jérôme Monnot, Bernard Ries |
| Subject & Discipline | Multidisciplinary Academic Open Research |
| Categories | Science & Mathematics |
| Publication Year | 2014 |
| License / Rights | Open Access / Creative Commons |
| Resource Verification | Listed PDF (Verification Pending) |
| Original Host Website |
HAL Open Science
(hal.science)
|
| File Format | application/pdf (Portable Document Format) |
| Language | EN |
| Catalog ID | DOC-245027 |
| Original Source Link | Visit Source Page on hal.science » |