• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
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
10.1007/978-3-319-41168-2_10
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

Related items

Showing items related by title and author.

  • Thumbnail
    The many facets of upper domination 
    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é
  • Thumbnail
    Upper Domination : Complexity and Approximation 
    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
  • Thumbnail
    On the Complexity Landscape of the Domination Chain 
    Bazgan, Cristina; Brankovic, Ljiljana; Casel, Katrin; Fernau, Henning (2016) Communication / Conférence
  • Thumbnail
    Domination chain: Characterisation, classical complexity, parameterised complexity and approximability 
    Bazgan, Cristina; Brankovic, Ljiljana; Casel, Katrin; Fernau, Henning (2016) Article accepté pour publication ou publié
  • Thumbnail
    Extension of Some Edge Graph Problems: Standard and Parameterized Complexity 
    Casel, Katrin; Fernau, Henning; Khosravian Ghadikolaei, Mehdi; Monnot, Jérôme; Sikora, Florian (2019) Communication / Conférence
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo