• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Thèses
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Thèses
  • 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

Résolution exacte du Problème de Coloration de Graphe et ses variantes

Exact algorithms for the Vertex Coloring Problem and its generalisations

Ternier, Ian-Christopher (2017), Résolution exacte du Problème de Coloration de Graphe et ses variantes, doctoral thesis prepared under the supervision of Gabrel, Virginie, Université Paris Dauphine

View/Open
2017PSLED060.pdf (1.241Mb)
Type
Thèse
Date
2017-11-21
Metadata
Show full item record
Author(s)
Ternier, Ian-Christopher
Under the direction of
Gabrel, Virginie
Abstract (FR)
Dans un graphe non orienté, le Problème de Coloration de Graphe (PCG) consiste à assigner à chaque sommet du graphe une couleur de telle sorte qu'aucune paire de sommets adjacents n'aient la même couleur et le nombre total de couleurs est minimisé. DSATUR est un algorithme exact efficace pour résoudre le PCG. Un de ses défauts est qu'une borne inférieure est calculée une seule fois au noeud racine de l'algorithme de branchement, et n'est jamais mise à jour. Notre nouvelle version de DSATUR surpasse l'état de l'art pour un ensemble d'instances aléatoires à haute densité, augmentant significativement la taille des instances résolues. Nous étudions trois formulations PLNE pour le Problème de la Somme Chromatique Minimale (PSCM). Chaque couleur est représentée par un entier naturel. Le PSCM cherche à minimiser la somme des cardinalités des sous-ensembles des sommets recevant la même couleur, pondérés par l'entier correspondant à la couleur, de telle sorte que toute paire de sommets adjacents reçoive des couleurs différentes. Nous nous concentrons sur l'étude d'une formulation étendue et proposons un algorithme de Branch-and-Price.
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 is an effective exact algorithm for the VCP. We introduce new lower bounding techniques enabling the computing of a lower bound at each node of the branching scheme. Our new DSATUR outperforms the state of the art for random VCP instances with high density, significantly increasing the size of solvable instances. Similar results can be achieved for a subset of high density DIMACS instances. We study three ILP formulations for the Minimum Sum Coloring Problem (MSCP). The problem is an extension of the classical Vertex Coloring Problem in which each color is represented by a positive natural number. The MSCP asks to minimize the sum of the cardinality of subsets of vertices receiving the same color, weighted by the index of the color, while ensuring that vertices linked by an edge receive different colors. We focus on studying an extended formulation and devise a complete Branch-and-Price algorithm.
Subjects / Keywords
Coloration de graphe; Dsatur; Séparation et Evaluation; Programmation Linéaire en Nombres Entiers; Génération de colonnes; Algorithme de génération de colonnes et branchement; Graph Coloring; Dsatur; Branch and Bound; Integer Linear Programming; Column Generation; Branch-And-Price

Related items

Showing items related by title and author.

  • Thumbnail
    An Improved DSATUR-Based Branch-and-Bound Algorithm for the Vertex Coloring Problem 
    Furini, Fabio; Gabrel, Virginie; Ternier, Ian-Christopher (2017) Article accepté pour publication ou publié
  • 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
    Lower Bounding Techniques for DSATUR-based Branch and Bound 
    Furini, Fabio; Gabrel, Virginie; Ternier, Ian-Christopher (2016) 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é
  • 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