Show simple item record

hal.structure.identifierCenter for Numerical Porous Media (NumPor) - King Abdullah University of Science and Technology
dc.contributor.authorAbouEisha, Hassan
hal.structure.identifierautre
dc.contributor.authorHussain, Shahid
hal.structure.identifierWarwick Mathematics Institute [WMI]
dc.contributor.authorLozin, Vadim
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.identifierUniversity of Fribourg
dc.contributor.authorRies, Bernard
hal.structure.identifierWarwick Mathematics Institute [WMI]
dc.contributor.authorZamaraev, Viktor
dc.date.accessioned2019-07-16T09:44:32Z
dc.date.available2019-07-16T09:44:32Z
dc.date.issued2018
dc.identifier.issn0178-4617
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/19239
dc.descriptionThe results of this paper previously appeared as extended abstracts in proceedings of the 8th International Conference on Combinatorial Optimization and Applications, COCOA 2014, and the 27th International Workshop on Combinatorial Algorithms, IWOCA 2016.en
dc.language.isoenen
dc.subjectUpper dominating seten
dc.subjectBoundary classen
dc.subjectComplexity dichotomyen
dc.subjectNP-harden
dc.subject.ddc005en
dc.titleUpper Domination: Towards a Dichotomy Through Boundary Propertiesen
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenAn 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.en
dc.relation.isversionofjnlnameAlgorithmica
dc.relation.isversionofjnlvol80en
dc.relation.isversionofjnlissue10en
dc.relation.isversionofjnldate2018-10
dc.relation.isversionofjnlpages2799-2817en
dc.relation.isversionofdoi10.1007/s00453-017-0346-9en
dc.relation.isversionofjnlpublisherSpringeren
dc.subject.ddclabelProgrammation, logiciels, organisation des donnéesen
dc.relation.forthcomingnonen
dc.relation.forthcomingprintnonen
dc.description.ssrncandidatenonen
dc.description.halcandidateouien
dc.description.readershiprechercheen
dc.description.audienceInternationalen
dc.relation.Isversionofjnlpeerreviewedouien
dc.relation.Isversionofjnlpeerreviewedouien
dc.date.updated2019-07-16T09:33:09Z
hal.identifierhal-02184833*
hal.version1*
hal.update.actionupdateFiles*
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