Show simple item record

dc.contributor.authorFurini, Fabio*
dc.contributor.authorGabrel, Virginie*
dc.contributor.authorTernier, Ian-Christopher*
dc.date.accessioned2017-03-17T17:39:25Z
dc.date.available2017-03-17T17:39:25Z
dc.date.issued2017
dc.identifier.issn0028-3045
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/16386
dc.language.isoenen
dc.subjectDSATUR
dc.subjectVertex Coloring Problem
dc.subjectgraph coloring
dc.subjectbranch-and-bound algorithm
dc.subjectbounding technique
dc.subjectcomputational experiments
dc.subjectexact algorithm
dc.subject.ddc511en
dc.titleAn Improved DSATUR-Based Branch-and-Bound Algorithm for the Vertex Coloring Problem
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 in such a way that two adjacent vertices do not share the same color and the total number of colors is minimized. DSATUR-based Branch-and-Bound algorithm (DSATUR) is an effective exact algorithm for the VCP. One of its main drawback is that a lower bound is computed only once and it is never updated. We introduce a reduced graph which allows the computation of lower bounds at nodes of the branching tree. We compare the effectiveness of different classical VCP bounds, plus a new lower bound based on the math formula -to- math formula mapping between VCPs and Stable Set Problems. Our new DSATUR outperforms the state of the art for random VCP instances with high density, significantly increasing the size of instances solved to proven optimality
dc.relation.isversionofjnlnameNetworks
dc.relation.isversionofjnlvol69
dc.relation.isversionofjnlissue1
dc.relation.isversionofjnldate2017
dc.relation.isversionofjnlpages124-141
dc.relation.isversionofdoi10.1002/net.21716
dc.relation.isversionofjnlpublisherJohn Wiley & Sons
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-06-02T16:59:45Z
hal.person.labIds*
hal.person.labIds*
hal.person.labIds*
hal.identifierhal-01492047*


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