Show simple item record

dc.contributor.authorBonnet, Édouard*
dc.contributor.authorFoucaud, Florent*
dc.contributor.authorKim, Eun Jung*
dc.contributor.authorSikora, Florian*
dc.date.accessioned2016-09-22T15:17:29Z
dc.date.available2016-09-22T15:17:29Z
dc.date.issued2015
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/15824
dc.language.isoenen
dc.subjectComplexityen
dc.subject.ddc003en
dc.titleComplexity of Grundy Coloring and Its Variantsen
dc.typeCommunication / Conférence
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 k. We show that Grundy Coloring can be solved in time O∗(2.443n) on graphs of order n. While the problem is known to be solvable in time f(k,w)⋅n for graphs of treewidth w, we prove that under the Exponential Time Hypothesis, it cannot be computed in time O∗(cw), for any constant c. We also study the parameterized complexity of Grundy Coloring parameterized by the number of colors, showing that it is in FPTfor graphs including chordal graphs, claw-free graphs, and graphs excluding a fixed minor.Finally, we consider two previously studied variants of Grundy Coloring, namely Weak Grundy Coloring and Connected Grundy Coloring. We show that Weak Grundy Coloring is fixed-parameter tractable with respect to the weak Grundy number. In stark contrast, it turns out that checking whether a given graph has connected Grundy number at least k is NP-complete already for k=7.en
dc.identifier.citationpages109-120en
dc.relation.ispartoftitleComputing and Combinatorics. 21st International Conference, COCOON 2015, Beijing, China, August 4-6, 2015, Proceedingsen
dc.relation.ispartofeditorXu, Dachuan
dc.relation.ispartofeditorDu, Donglei
dc.relation.ispartofeditorDu, Ding-Zhu
dc.relation.ispartofpublnameSpringer International Publishingen
dc.relation.ispartofdate2015
dc.relation.ispartofurl10.1007/978-3-319-21398-9en
dc.identifier.urlsitehttp://arxiv.org/abs/1407.5336v3en
dc.subject.ddclabelRecherche opérationnelleen
dc.relation.ispartofisbn978-3-319-21397-2en
dc.relation.conftitle21st International Conference on Computing and Combinatorics, COCOON 2015en
dc.relation.confdate2015-08
dc.relation.confcityBeijingen
dc.relation.confcountryChinaen
dc.relation.forthcomingnonen
dc.identifier.doi10.1007/978-3-319-21398-9_9en
dc.description.ssrncandidatenonen
dc.description.halcandidateouien
dc.description.readershiprechercheen
dc.description.audienceInternationalen
dc.relation.Isversionofjnlpeerreviewednonen
dc.relation.Isversionofjnlpeerreviewednonen
dc.date.updated2016-07-18T10:28:28Z
hal.person.labIds989*
hal.person.labIds857*
hal.person.labIds989*
hal.person.labIds989*
hal.identifierhal-01370531*


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