Show simple item record

dc.contributor.authorFurini, Fabio*
dc.contributor.authorGabrel, Virginie*
dc.contributor.authorTernier, Ian-Christopher*
dc.date.accessioned2017-03-17T16:45:50Z
dc.date.available2017-03-17T16:45:50Z
dc.date.issued2016
dc.identifier.issn1571-0653
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/16383
dc.language.isoenen
dc.subjectGraph Coloring
dc.subjectDSATUR
dc.subjectBranch and Bound
dc.subject.ddc511en
dc.titleLower Bounding Techniques for DSATUR-based Branch and Bound
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenGiven an undirected graph, the Vertex Coloring Problem (VCP) consists of assigning a color to each vertex of the graph such that two adjacent vertices do not share the same color and the total number of colors is minimized. DSATUR-based Branch-and-Bound is a well-known exact algorithm for the VCP. One of its main drawbacks is that a lower bound (equal to the size of a maximal clique) is computed once at the root of the branching scheme and it is never updated during the execution of the algorithm. In this article, we show how to update the lower bound and we compare the efficiency of several lower bounding techniques.
dc.relation.isversionofjnlnameElectronic Notes in Discrete Mathematics
dc.relation.isversionofjnlvol52
dc.relation.isversionofjnldate2016
dc.relation.isversionofjnlpages149-156
dc.relation.isversionofdoi10.1016/j.endm.2016.03.020
dc.relation.isversionofjnlpublisherInstitute of Mathematical Statistics
dc.subject.ddclabelPrincipes généraux des mathématiquesen
dc.relation.forthcomingnonen
dc.relation.forthcomingprintnonen
dc.description.ssrncandidatenon
dc.description.halcandidateoui
dc.description.readershiprecherche
dc.description.audienceInternational
dc.relation.Isversionofjnlpeerreviewedoui
dc.date.updated2017-07-27T16:12:43Z
hal.person.labIds989*
hal.person.labIds989*
hal.person.labIds989*
hal.faultCode{"duplicate-entry":{"hal-01337588":{"doi":"1.0"}}}


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