| Title |
|
Algorithmic Aspects of Upper Domination: A Parameterised Perspective |
|
|
| Publication Date |
|
| Author(s) |
|
| Editor |
|
Editor(s): Riccardo Dondi, Guillaume Fertin and Giancarlo Mauri |
|
|
| Type of document |
|
| Language |
|
| Entity Type |
|
| Publisher |
|
| Place of publication |
|
| Edition |
|
| Series |
|
Lecture Notes in Computer Science |
|
|
| DOI |
|
10.1007/978-3-319-41168-2_10 |
|
|
| UNE publication id |
|
| Abstract |
This paper studies Upper Domination, i.e., the problem of computing the maximum cardinality of a minimal dominating set in a graph, with a focus on parameterised complexity. Our main results include W[1]-hardness for Upper Domination, contrasting FPT membership for the parameterised dual Co-Upper Domination. The study of structural properties also yields some insight into Upper Total Domination. We further consider graphs of bounded degree and derive upper and lower bounds for kernelisation. |
|
|
| Link |
|
| Citation |
|
Algorithmic Aspects in Information and Management: 11th International Conference, AAIM 2016, Bergamo, Italy, July 18-20, 2016, Proceedings, p. 113-124 |
|
|
| ISBN |
|
| Start page |
|
| End page |
|