Show simple item record

dc.contributor.authorAboueisha, Hassan
dc.contributor.authorHussain, Shahid
dc.contributor.authorLozin, Vadim
dc.contributor.authorMonnot, Jérôme
dc.contributor.authorRies, Bernard
dc.contributor.authorZamaraev, Viktor
dc.date.accessioned2016-09-21T15:42:01Z
dc.date.available2016-09-21T15:42:01Z
dc.date.issued2016
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/15817
dc.descriptionLNCS n°9843en
dc.language.isoenen
dc.subjectGraphen
dc.subjectalgrithmen
dc.subjectNP-harden
dc.subject.ddc003en
dc.titleA Boundary Property for Upper Dominationen
dc.typeCommunication / Conférence
dc.description.abstractenAn upper dominating set in a graph is a minimal (with respect to set inclusion) dominating set of maximum cardinality. The problem of finding an upper dominating set is generally NP-hard, but can be solved in polynomial time in some restricted graph classes, such as P4-free graphs or 2K2-free graphs. For classes defined by finitely many forbidden induced subgraphs, the boundary separating difficult instances of the problem from polynomially solvable ones consists of the so called boundary classes. However, none of such classes has been identified so far for the upper dominating set problem. In the present paper, we discover the first boundary class for this problem.en
dc.identifier.citationpages229-240en
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_18en
dc.description.ssrncandidatenonen
dc.description.halcandidateouien
dc.description.readershiprechercheen
dc.description.audienceInternationalen
dc.relation.Isversionofjnlpeerreviewednonen
dc.relation.Isversionofjnlpeerreviewednonen
dc.date.updated2016-09-12T16:20:26Z
hal.person.labIds230273
hal.person.labIds230273
hal.person.labIds3526
hal.person.labIds989
hal.person.labIds207238
hal.person.labIds3526
hal.identifierhal-01370014*


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