• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
Thumbnail - Request a copy

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
2017
Journal name
Networks
Volume
69
Number
1
Publisher
John Wiley & Sons
Pages
124-141
Publication identifier
10.1002/net.21716
Metadata
Show full item record
Author(s)
Furini, Fabio

Gabrel, Virginie

Ternier, Ian-Christopher
Abstract (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 optimality
Subjects / Keywords
DSATUR; Vertex Coloring Problem; graph coloring; branch-and-bound algorithm; bounding technique; computational experiments; exact algorithm

Related items

Showing items related by title and author.

  • Thumbnail
    Lower Bounding Techniques for DSATUR-based Branch and Bound 
    Furini, Fabio; Gabrel, Virginie; Ternier, Ian-Christopher (2016) Article accepté pour publication ou publié
  • Thumbnail
    Résolution exacte du Problème de Coloration de Graphe et ses variantes 
    Ternier, Ian-Christopher (2017-11-21) Thèse
  • Thumbnail
    Bornes inférieures sur un algorithme exact basé sur DSATUR résolvant la coloration 
    Ternier, Ian-Christopher; Furini, Fabio; Gabrel, Virginie (2015) Communication / Conférence
  • Thumbnail
    A new branch-and-bound algorithm for the maximum edge-weighted clique problem 
    San Segundo, Pablo; Coniglio, Stefano; Furini, Fabio; Ljubić, Ivana (2019) Article accepté pour publication ou publié
  • Thumbnail
    An exact algorithm for the Partition Coloring Problem 
    Furini, Fabio; Malaguti, Enrico; Santini, Alberto (2018) Article accepté pour publication ou publié
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo