• 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

Upper Domination: Towards a Dichotomy Through Boundary Properties

AbouEisha, Hassan; Hussain, Shahid; Lozin, Vadim; Monnot, Jérôme; Ries, Bernard; Zamaraev, Viktor (2018), Upper Domination: Towards a Dichotomy Through Boundary Properties, Algorithmica, 80, 10, p. 2799-2817. 10.1007/s00453-017-0346-9

View/Open
Upper_domination.pdf (201.7Kb)
Type
Article accepté pour publication ou publié
Date
2018
Journal name
Algorithmica
Volume
80
Number
10
Publisher
Springer
Pages
2799-2817
Publication identifier
10.1007/s00453-017-0346-9
Metadata
Show full item record
Author(s)
AbouEisha, Hassan
Center for Numerical Porous Media (NumPor) - King Abdullah University of Science and Technology
Hussain, Shahid
autre
Lozin, Vadim
Warwick Mathematics Institute [WMI]
Monnot, Jérôme cc
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Ries, Bernard

Zamaraev, Viktor
Warwick Mathematics Institute [WMI]
Abstract (EN)
An upper dominating set in a graph is a minimal dominating set of maximum cardinality. The problem of finding an upper dominating set is generally NP-hard. We study the complexity of this problem in finitely defined classes of graphs and conjecture that the problem admits a complexity dichotomy in this family. A helpful tool to study the complexity of an algorithmic problem is the notion of boundary classes. However, none of such classes has been identified so far for the upper dominating set problem. We discover the first boundary class for this problem and prove the dichotomy for monogenic classes.
Subjects / Keywords
Upper dominating set; Boundary class; Complexity dichotomy; NP-hard

Related items

Showing items related by title and author.

  • Thumbnail
    A Dichotomy for Upper Domination in Monogenic Classes 
    AbouEisha, Hassan; Hussain, Shahid; Lozin, Vadim; Monnot, Jérôme; Ries, Bernard (2014) Communication / Conférence
  • Thumbnail
    A Boundary Property for Upper Domination 
    AbouEisha, Hassan; Hussain, Shahid; Lozin, Vadim; Monnot, Jérôme; Ries, Bernard; Zamaraev, Viktor (2016) Communication / Conférence
  • Thumbnail
    On the maximum independent set problem in subclasses of subcubic graphs 
    Ries, Bernard; Monnot, Jérôme; Lozin, Vadim (2015) Article accepté pour publication ou publié
  • Thumbnail
    On the Maximum Independent Set Problem in Subclasses of Subcubic Graphs 
    Lozin, Vadim; Monnot, Jérôme; Ries, Bernard (2013) Communication / Conférence
  • Thumbnail
    Colouring vertices of triangle-free graphs without forests 
    Ries, Bernard; Raman, Rajiv; Lozin, Vadim; Dabrowski, Konrad Kazimierz (2012) Article accepté pour publication ou publié
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