Algorithmic Aspects of Upper Domination: A Parameterized Perspective

Thumbnail
Date
2016
Description
LNCS n°9778
Lien vers un document non conservé dans cette base
https://arxiv.org/abs/1506.07260v1
Indexation documentaire
Recherche opérationnelle
Subject
Upper Domination; Graphs; Approximation
Réf version publiée
http://dx.doi.org/10.1007/978-3-319-41168-2_10
Titre de l'ouvrage
Algorithmic Aspects in Information and Management. 11th International Conference, AAIM 2016, Bergamo, Italy, July 18-20, 2016, Proceedings
Auteur
Riccardo Dondi, Guillaume Fertin, Giancarlo Mauri
Nom de l'éditeur
Springer
Ville de l'éditeur
Berlin Heidelberg
Année
2016
ISBN
978-3-319-41167-5
URL de l'ouvrage
10.1007/978-3-319-41168-2
URI
https://basepub.dauphine.fr/handle/123456789/15913
Collections
Métadonnées
Afficher la notice complète
Auteur
Bazgan, Cristina
989 Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Brankovic, L.
Casel, K.
Fernau, H.
Jansen, K.
Klein, K-M.
Lampis, Michail
Liedloff, M.
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
Nombre de pages du document
113-124
Résumé en anglais
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.