• 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

Solving vertex coloring problems as maximum weight stable set problems

Cornaz, Denis; Furini, Fabio; Malaguti, Enrico (2017), Solving vertex coloring problems as maximum weight stable set problems, Discrete Applied Mathematics, 217, 2, p. 151-162. 10.1016/j.dam.2016.09.018

View/Open
4969.pdf (259.5Kb)
Type
Article accepté pour publication ou publié
Date
2017
Journal name
Discrete Applied Mathematics
Volume
217
Number
2
Publisher
Elsevier
Pages
151-162
Publication identifier
10.1016/j.dam.2016.09.018
Metadata
Show full item record
Author(s)
Cornaz, Denis
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Furini, Fabio
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Malaguti, Enrico
Abstract (EN)
In Vertex Coloring Problems, one is required to assign a color to each vertex of an undirected graph in such a way that adjacent vertices receive different colors, and the objective is to minimize the cost of the used colors. In this work we solve four different coloring problems formulated as Maximum Weight Stable Set Problems on an associated graph. We exploit the transformation proposed by Cornaz and Jost (2008), where given a graph GG, an auxiliary graph View the MathML sourceGˆ is constructed, such that the family of all stable sets of View the MathML sourceGˆ is in one-to-one correspondence with the family of all feasible colorings of GG. The transformation in Cornaz and Jost (2008) was originally proposed for the classical Vertex Coloring and the Max-Coloring problems; we extend it to the Equitable Coloring Problem and the Bin Packing Problem with Conflicts. We discuss the relation between the Maximum Weight Stable formulation and a polynomial-size formulation for the VCP, proposed by Campêlo et al. (2008) and called the Representative formulation. We report extensive computational experiments on benchmark instances of the four problems, and compare the solution method with the state-of-the-art algorithms. By exploiting the proposed method, we largely outperform the state-of-the-art algorithm for the Max-coloring Problem, and we are able to solve, for the first time to proven optimality, 14 Max-coloring and 2 Equitable Coloring instances.
Subjects / Keywords
Vertex coloring; Stable set; Mixed integer linear programming; Computational experiments

Related items

Showing items related by title and author.

  • Thumbnail
    The vertex k-cut problem 
    Cornaz, Denis; Furini, Fabio; Lacroix, Mathieu; Malaguti, Enrico; Mahjoub, Ali Ridha; Martin, Sébastien (2019) Article accepté pour publication ou publié
  • Thumbnail
    Mathematical formulations for the Balanced Vertex k-Separator Problem 
    Cornaz, Denis; Furini, Fabio; Lacroix, Mathieu; Malaguti, Enrico; Mahjoub, Ali Ridha; Martin, Sébastien (2014) Communication / Conférence
  • Thumbnail
    The vertex k-cut problem 
    Cornaz, Denis; Furini, Fabio; Lacroix, Mathieu; Malaguti, Enrico; Mahjoub, Ali Ridha; Martin, Sébastien (2019) Article accepté pour publication ou publié
  • Thumbnail
    A note on selective line-graphs and partition colorings 
    Cornaz, Denis; Furini, Fabio; Malaguti, Enrico; Santini, Alberto (2019) Article accepté pour publication ou publié
  • Thumbnail
    Solving the Temporal Knapsack Problem via Recursive Dantzig–Wolfe Reformulation 
    Caprara, Alberto; Furini, Fabio; Malaguti, Enrico; Traversi, Emiliano (2016) 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