Show simple item record

dc.contributor.authorBazgan, Cristina
dc.contributor.authorBrankovic, Ljiljana
dc.contributor.authorCasel, Katrin
dc.contributor.authorFernau, Henning
dc.date.accessioned2017-01-11T09:50:23Z
dc.date.available2017-01-11T09:50:23Z
dc.date.issued2016
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/16146
dc.descriptionin Springer series Lecture Notes in Computer Science, vol. 9602en
dc.language.isoenen
dc.subjectdominationen
dc.subjectcomplexityen
dc.subject.ddc003en
dc.subject.classificationjelC.C4.C44en
dc.titleOn the Complexity Landscape of the Domination Chainen
dc.typeCommunication / Conférence
dc.description.abstractenIn 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.en
dc.identifier.citationpages61-72en
dc.relation.ispartoftitleAlgorithms and Discrete Applied Mathematicsen
dc.relation.ispartofeditorGovindarajan, Sathish
dc.relation.ispartofeditorMaheshwari, Anil
dc.relation.ispartofpublnameSpringeren
dc.relation.ispartofpublcityChamen
dc.relation.ispartofdate2016
dc.relation.ispartofpages369en
dc.relation.ispartofurl10.1007/978-3-319-29221-2en
dc.contributor.countryeditoruniversityotherAUSTRALIA
dc.contributor.countryeditoruniversityotherGERMANY
dc.subject.ddclabelRecherche opérationnelleen
dc.relation.ispartofisbn978-3-319-29220-5en
dc.relation.conftitleSecond International Conference, CALDAM 2016en
dc.relation.confdate2016-02
dc.relation.confcityThiruvananthapuramen
dc.relation.confcountryIndiaen
dc.relation.forthcomingnonen
dc.identifier.doi10.1007/978-3-319-29221-2_6en
dc.description.ssrncandidatenonen
dc.description.halcandidateouien
dc.description.readershiprechercheen
dc.description.audienceInternationalen
dc.relation.Isversionofjnlpeerreviewednonen
dc.relation.Isversionofjnlpeerreviewednonen
dc.date.updated2017-01-11T09:34:52Z
hal.person.labIds989
hal.person.labIds59084
hal.person.labIds87731
hal.person.labIds87731
hal.identifierhal-01431677*


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record