Show simple item record

hal.structure.identifierInstitute for Computer Science and Control [Budapest] [SZTAKI]
dc.contributor.authorBonnet, Édouard
HAL ID: 171728
ORCID: 0000-0002-1653-5822
*
hal.structure.identifierLaboratoire d'Informatique, de Modélisation et d'optimisation des Systèmes [LIMOS]
dc.contributor.authorFoucaud, Florent
HAL ID: 169708
*
hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorKim, Eun Jung*
hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorSikora, Florian
HAL ID: 742949
ORCID: 0000-0003-2670-6258
*
dc.date.accessioned2019-04-19T15:11:25Z
dc.date.available2019-04-19T15:11:25Z
dc.date.issued2018
dc.identifier.issn0166-218X
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/18724
dc.language.isoenen
dc.subjectGrundy coloringen
dc.subjectComputational complexityen
dc.subjectWeak Grundyen
dc.subjectConnected Grundyen
dc.subjectExact algorithmen
dc.subjectParameterized complexityen
dc.subject.ddc511en
dc.titleComplexity of Grundy coloring and its variantsen
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenThe Grundy number of a graph is the maximum number of colors used by the greedy coloring algorithm over all vertex orderings. In this paper, we study the computational complexity of Grundy Coloring, the problem of determining whether a given graph has Grundy number at least . We also study the variants Weak Grundy Coloring (where the coloring is not necessarily proper) and Connected Grundy Coloring (where at each step of the greedy coloring algorithm, the subgraph induced by the colored vertices must be connected).en
dc.relation.isversionofjnlnameDiscrete Applied Mathematics
dc.relation.isversionofjnlvol243en
dc.relation.isversionofjnldate2018-07
dc.relation.isversionofjnlpages99-114en
dc.relation.isversionofdoi10.1016/j.dam.2017.12.022en
dc.relation.isversionofjnlpublisherElsevieren
dc.subject.ddclabelPrincipes généraux des mathématiquesen
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-03-22T09:20:36Z
hal.identifierhal-02104874*
hal.version1*
hal.update.actionupdateFiles*
hal.update.actionupdateMetadata*
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