• 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

On the Complexity Landscape of the Domination Chain

Thumbnail
Date
2016
Notes
in Springer series Lecture Notes in Computer Science, vol. 9602
Dewey
Recherche opérationnelle
Sujet
domination; complexity
JEL code
C.C4.C44
DOI
http://dx.doi.org/10.1007/978-3-319-29221-2_6
Conference name
Second International Conference, CALDAM 2016
Conference date
02-2016
Conference city
Thiruvananthapuram
Conference country
India
Book title
Algorithms and Discrete Applied Mathematics
Author
Govindarajan, Sathish; Maheshwari, Anil
Publisher
Springer
Publisher city
Cham
Year
2016
Pages number
369
ISBN
978-3-319-29220-5
Book URL
10.1007/978-3-319-29221-2
URI
https://basepub.dauphine.fr/handle/123456789/16146
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
59084 University of Newcastle
Casel, Katrin
status unknown
Fernau, Henning
status unknown
Type
Communication / Conférence
Item number of pages
61-72
Abstract (EN)
In this paper, we survey and supplement the complexity landscape of the domination chain parameters as a whole, including classifications according to approximability and parameterised complexity. Moreover, we provide clear pointers to yet open questions. As this posed the majority of hitherto unsettled problems, we focus on Upper Irredundance and Lower Irredundance that correspond to finding the largest irredundant set and resp. the smallest maximal irredundant set. The problems are proved NP-hard even for planar cubic graphs. While Lower Irredundance is proved not clog(n)-approximable in polynomial time unless NP⊆DTIME(nloglogn), no such result is known for Upper Irredundance. Their complementary versions are constant-factor approximable in polynomial time. All these four versions are APX-hard even on cubic graphs.

  • 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.