Show simple item record

hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorBazgan, Cristina*
hal.structure.identifier
dc.contributor.authorBrankovic, Ljiljana*
hal.structure.identifier
dc.contributor.authorCasel, Katrin*
hal.structure.identifier
dc.contributor.authorFernau, Henning*
hal.structure.identifier
dc.contributor.authorJansen, Klaus*
hal.structure.identifier
dc.contributor.authorKlein, Kim-Manuel*
hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorLampis, Michael
HAL ID: 182546
ORCID: 0000-0002-5791-0887
*
hal.structure.identifierLaboratoire d'Informatique Fondamentale d'Orléans [LIFO]
dc.contributor.authorLiedloff, Mathieu
HAL ID: 2195
*
hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorMonnot, Jérôme
HAL ID: 178759
ORCID: 0000-0002-7452-6553
*
hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorPaschos, Vangelis*
dc.date.accessioned2016-09-22T15:09:37Z
dc.date.available2016-09-22T15:09:37Z
dc.date.issued2016
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/15822
dc.descriptionLNCS n°9843en
dc.language.isoenen
dc.subjectUpper Dominationen
dc.subjectGraphsen
dc.subjectApproximationen
dc.subjectComplexityen
dc.subject.ddc003en
dc.titleUpper Domination : Complexity and Approximationen
dc.typeCommunication / Conférence
dc.description.abstractenWe consider Upper Domination, the problem of finding a maximum cardinality minimal dominating set in a graph. We show that this problem does not admit an n1−ϵ approximation for any ϵ>0, making it significantly harder than Dominating Set, while it remains hard even on severely restricted special cases, such as cubic graphs (APX-hard), and planar subcubic graphs (NP-hard). We complement our negative results by showing that the problem admits an O(Δ) approximation on graphs of maximum degree Δ, as well as an EPTAS on planar graphs. Along the way, we also derive essentially tight n1−1d upper and lower bounds on the approximability of the related problem Maximum Minimal Hitting Set on d-uniform hypergraphs, generalising known results for Maximum Minimal Vertex Cover.en
dc.identifier.citationpages241-252en
dc.relation.ispartoftitleCombinatorial Algorithms. 27th International Workshop, IWOCA 2016, Helsinki, Finland, August 17-19, 2016, Proceedingsen
dc.relation.ispartofeditorMäkinen, Veli
dc.relation.ispartofeditorPuglisi, Simon J.
dc.relation.ispartofeditorSalmela, Leena
dc.relation.ispartofpublnameSpringeren
dc.relation.ispartofpublcityBerlin Heidelbergen
dc.relation.ispartofdate2016
dc.relation.ispartofurl10.1007/978-3-319-44543-4en
dc.subject.ddclabelRecherche opérationnelleen
dc.relation.ispartofisbn978-3-319-44542-7en
dc.relation.conftitle27th International Workshop on Combinatorial Algorithms, IWOCA 2016en
dc.relation.confdate2016-08
dc.relation.confcityHelsinkien
dc.relation.confcountryFinlanden
dc.relation.forthcomingnonen
dc.identifier.doi10.1007/978-3-319-44543-4_19en
dc.description.ssrncandidatenonen
dc.description.halcandidateouien
dc.description.readershiprechercheen
dc.description.audienceInternationalen
dc.relation.Isversionofjnlpeerreviewednonen
dc.relation.Isversionofjnlpeerreviewednonen
dc.date.updated2016-09-12T16:26:05Z
hal.faultCode{"duplicate-entry":{"hal-01367856":{"doi":"1.0"}}}
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record