• français
    • English
  • English 
    • français
    • English
  • Login
JavaScript is disabled for your browser. Some features of this site may not work without it.
BIRD Home

Browse

This CollectionBy Issue DateAuthorsTitlesSubjectsJournals BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesSubjectsJournals

My Account

Login

Statistics

View Usage Statistics

An Improved DSATUR-Based Branch-and-Bound Algorithm for the Vertex Coloring Problem

Thumbnail
Date
2017
Dewey
Principes généraux des mathématiques
Sujet
DSATUR; Vertex Coloring Problem; graph coloring; branch-and-bound algorithm; bounding technique; computational experiments; exact algorithm
Journal issue
Networks
Volume
69
Number
1
Publication date
2017
Article pages
124-141
Publisher
John Wiley & Sons
DOI
http://dx.doi.org/10.1002/net.21716
URI
https://basepub.dauphine.fr/handle/123456789/16386
Collections
  • LAMSADE : Publications
Metadata
Show full item record
Author
Furini, Fabio
Gabrel, Virginie
Ternier, Ian-Christopher
Type
Article accepté pour publication ou publié
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

  • Accueil Bibliothèque
  • Site de l'Université Paris-Dauphine
  • Contact
SCD Paris Dauphine - Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16

 Content on this site is licensed under a Creative Commons 2.0 France (CC BY-NC-ND 2.0) license.