Thumbnail - No thumbnail

Algorithmic Aspects of Upper Domination: A Parameterized Perspective

Bazgan, Cristina; Brankovic, Ljiljana; Casel, Katrin; Fernau, Henning; Jansen, Klaus; Lampis, Michael; Liedloff, Mathieu; Monnot, Jérôme; Paschos, Vangelis (2016), Algorithmic Aspects of Upper Domination: A Parameterized Perspective, in Riccardo Dondi, Guillaume Fertin, Giancarlo Mauri, Algorithmic Aspects in Information and Management. 11th International Conference, AAIM 2016, Bergamo, Italy, July 18-20, 2016, Proceedings, Springer : Berlin Heidelberg, p. 113-124. 10.1007/978-3-319-41168-2_10

Type
Communication / Conférence
External document link
https://arxiv.org/abs/1506.07260v1
Date
2016
Book title
Algorithmic Aspects in Information and Management. 11th International Conference, AAIM 2016, Bergamo, Italy, July 18-20, 2016, Proceedings
Book author
Riccardo Dondi, Guillaume Fertin, Giancarlo Mauri
Publisher
Springer
Published in
Berlin Heidelberg
ISBN
978-3-319-41167-5
Pages
113-124
Publication identifier
Metadata
Show full item record
Author(s)
Bazgan, Cristina
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 cc

Liedloff, Mathieu

Monnot, Jérôme cc
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Paschos, Vangelis
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.
Subjects / Keywords
Upper Domination; Graphs; Approximation