Thumbnail - Request a copy

Lower Bounding Techniques for DSATUR-based Branch and Bound

Furini, Fabio; Gabrel, Virginie; Ternier, Ian-Christopher (2016), Lower Bounding Techniques for DSATUR-based Branch and Bound, Electronic Notes in Discrete Mathematics, 52, p. 149-156. 10.1016/j.endm.2016.03.020

Type
Article accepté pour publication ou publié
Date
2016
Journal name
Electronic Notes in Discrete Mathematics
Volume
52
Publisher
Institute of Mathematical Statistics
Pages
149-156
Publication identifier
Metadata
Show full item record
Author(s)
Furini, Fabio
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Gabrel, Virginie
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Ternier, Ian-Christopher
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Abstract (EN)
Given 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.
Subjects / Keywords
Graph Coloring; DSATUR; Branch and Bound