• français
    • English
  • English 
    • français
    • English
  • Login
JavaScript is disabled for your browser. Some features of this site may not work without it.
BIRD Home

Browse

This CollectionBy Issue DateAuthorsTitlesSubjectsJournals BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesSubjectsJournals

My Account

Login

Statistics

View Usage Statistics

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
  • LAMSADE : Publications
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.

  • Accueil Bibliothèque
  • Site de l'Université Paris-Dauphine
  • Contact
SCD Paris Dauphine - Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16

 Content on this site is licensed under a Creative Commons 2.0 France (CC BY-NC-ND 2.0) license.