Bazgan, Cristina

Brankovic, Ljiljana

Casel, Katrin

Fernau, Henning

Jansen, Klaus

Klein, Kim-Manuel

Lampis, Michael

Liedloff, Mathieu

Monnot, Jérôme

Paschos, Vangelis Th

2016

<p>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.</p>

Algorithmic Aspects in Information and Management: 11th International Conference, AAIM 2016, Bergamo, Italy, July 18-20, 2016, Proceedings, p. 113-124

9783319411675

9783319411682

https://hdl.handle.net/1959.11/52012

Springer

Lecture Notes in Computer Science

1

Algorithmic Aspects of Upper Domination: A Parameterised Perspective

Conference Publication

Publication