Show simple item record

dc.contributor.authorBonnet, Edouard
dc.contributor.authorFoucaud, Florent
dc.contributor.authorKim, Eun Jung
dc.contributor.authorSikora, Florian
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.person.labIds220549
hal.person.labIds857
hal.person.labIds989
hal.person.labIds989
hal.identifierhal-02104874*


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record