Algorithmic Aspects of Upper Domination: A Parameterized Perspective

Thumbnail
Date
2016
Notes
LNCS n°9778
Link to item file
https://arxiv.org/abs/1506.07260v1
Dewey
Recherche opérationnelle
Sujet
Upper Domination; Graphs; Approximation
DOI
http://dx.doi.org/10.1007/978-3-319-41168-2_10
Book title
Algorithmic Aspects in Information and Management. 11th International Conference, AAIM 2016, Bergamo, Italy, July 18-20, 2016, Proceedings
Author
Riccardo Dondi, Guillaume Fertin, Giancarlo Mauri
Publisher
Springer
Publisher city
Berlin Heidelberg
Year
2016
ISBN
978-3-319-41167-5
Book URL
10.1007/978-3-319-41168-2
URI
https://basepub.dauphine.fr/handle/123456789/15913
Collections
Metadata
Show full item record
Author
Bazgan, Cristina
989 Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Brankovic, Ljiljana
Casel, Katrin
Fernau, Henning
Jansen, Klaus
Lampis, Michael
Liedloff, Mathieu
Monnot, Jérôme
989 Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Paschos, Vangelis
Type
Communication / Conférence
Item number of pages
113-124
Abstract (EN)
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.