• 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

On some applications of the selective graph coloring problem

Thumbnail
Date
2015
Dewey
Recherche opérationnelle
Sujet
Combinatorial optimization; Graph theory; Partition coloring; Selective coloring; Computational complexity
Journal issue
European Journal of Operational Research
Volume
240
Number
2
Publication date
2015
Article pages
307-314
Publisher
Elsevier
DOI
http://dx.doi.org/10.1016/j.ejor.2014.05.011
URI
https://basepub.dauphine.fr/handle/123456789/15676
Collections
  • LAMSADE : Publications
Metadata
Show full item record
Author
Demange, Marc
24359 ESSEC Business School
Ekim, Tinaz
252064 Industrial Engineering Department [Istanbul]
Ries, Bernard
989 Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Tanasescu, Cerasela
24359 ESSEC Business School
Type
Article accepté pour publication ou publié
Abstract (EN)
In this paper we present the Selective Graph Coloring Problem, a generalization of the standard graph coloring problem as well as several of its possible applications. Given a graph with a partition of its vertex set into several clusters, we want to select one vertex per cluster such that the chromatic number of the subgraph induced by the selected vertices is minimum. This problem appeared in the literature under different names for specific models and its complexity has recently been studied for different classes of graphs. Here, we describe different models – some already discussed in previous papers and some new ones – in very different contexts under a unified framework based on this graph problem. We point out similarities between these models, offering a new approach to solve them, and show some generic situations where the selective graph coloring problem may be used. We focus on specific graph classes motivated by each model, and we briefly discuss the complexity of the selective graph coloring problem in each one of these graph classes and point out interesting future research directions.

  • 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.