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érenceExternal document link
https://arxiv.org/abs/1506.07260v1Date
2016Book title
Algorithmic Aspects in Information and Management. 11th International Conference, AAIM 2016, Bergamo, Italy, July 18-20, 2016, ProceedingsBook author
Riccardo Dondi, Guillaume Fertin, Giancarlo MauriPublisher
Springer
Published in
Berlin Heidelberg
ISBN
978-3-319-41167-5
Pages
113-124
Publication identifier
Metadata
Show full item recordAuthor(s)
Bazgan, CristinaLaboratoire 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

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; ApproximationRelated items
Showing items related by title and author.
-
Bazgan, Cristina; Brankovic, Ljiljana; Casel, Katrin; Fernau, Henning; Jansen, Klaus; Klein, Kim-Manuel; Lampis, Michael; Liedloff, Mathieu; Monnot, Jérôme; Paschos, Vangelis (2018) Article accepté pour publication ou publié
-
Bazgan, Cristina; Brankovic, Ljiljana; Casel, Katrin; Fernau, Henning; Jansen, Klaus; Klein, Kim-Manuel; Lampis, Michael; Liedloff, Mathieu; Monnot, Jérôme; Paschos, Vangelis (2016) Communication / Conférence
-
Bazgan, Cristina; Brankovic, Ljiljana; Casel, Katrin; Fernau, Henning (2016) Communication / Conférence
-
Bazgan, Cristina; Brankovic, Ljiljana; Casel, Katrin; Fernau, Henning (2016) Article accepté pour publication ou publié
-
Casel, Katrin; Fernau, Henning; Khosravian Ghadikolaei, Mehdi; Monnot, Jérôme; Sikora, Florian (2019) Communication / Conférence