An Improved DSATUR-Based Branch-and-Bound Algorithm for the Vertex Coloring Problem
Furini, Fabio; Gabrel, Virginie; Ternier, Ian-Christopher (2017), An Improved DSATUR-Based Branch-and-Bound Algorithm for the Vertex Coloring Problem, Networks, 69, 1, p. 124-141. 10.1002/net.21716
Type
Article accepté pour publication ou publiéDate
2017Journal name
NetworksVolume
69Number
1Publisher
John Wiley & Sons
Pages
124-141
Publication identifier
Metadata
Show full item recordAbstract (EN)
Given 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 optimalitySubjects / Keywords
DSATUR; Vertex Coloring Problem; graph coloring; branch-and-bound algorithm; bounding technique; computational experiments; exact algorithmRelated items
Showing items related by title and author.
-
Furini, Fabio; Gabrel, Virginie; Ternier, Ian-Christopher (2016) Article accepté pour publication ou publié
-
Ternier, Ian-Christopher (2017-11-21) Thèse
-
Ternier, Ian-Christopher; Furini, Fabio; Gabrel, Virginie (2015) Communication / Conférence
-
San Segundo, Pablo; Coniglio, Stefano; Furini, Fabio; Ljubić, Ivana (2019) Article accepté pour publication ou publié
-
Furini, Fabio; Malaguti, Enrico; Santini, Alberto (2018) Article accepté pour publication ou publié