Selective graph coloring problem: applications and complexity
Event details
| Date | 12.02.2016 |
| Hour | 11:00 › 12:00 |
| Speaker |
Ass. Prof. Marc Demange, RMIT University, School of Science - Mathematical and Geospatial Sciences, Melbourne - Australia Bio: HDR (Computer Science), Paris-Dauphine University PHD (Doctoral Thesis), Computer Science, Paris I UniversityResearch Master (DEA) Modeling and Mathematical Methods for Economy, Paris I University-Ecole PolytechniqueAgrégation (French Diploma for Teaching), Mathematics (Probability)Ecole Normale Supérieure de Cachan (French school for teaching and research career), Mathematics |
| Location | |
| Category | Conferences - Seminars |
In this talk I will present the minimum Selective Graph Coloring Problem, a generalization of the standard graph coloring problem as well as several of its possible applications and related complexity results. Given a graph with a partition of its vertex set into several clusters, one wants 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.
Here I will 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. Each model motivates the problem in some graph classes and I will discuss the related complexity in these classes. I will also conclude by introducing the maximum version of the problem. This talk covers recent papers co-authored with T. Ekim (Bogazici University, Istanbul), J. Monnot (CNRS, France), B. Ries (University of Fribourg), C. Tanasescu (RMIT University, Australia) and P. Pop (University of Baia Mare, Romania).
Here I will 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. Each model motivates the problem in some graph classes and I will discuss the related complexity in these classes. I will also conclude by introducing the maximum version of the problem. This talk covers recent papers co-authored with T. Ekim (Bogazici University, Istanbul), J. Monnot (CNRS, France), B. Ries (University of Fribourg), C. Tanasescu (RMIT University, Australia) and P. Pop (University of Baia Mare, Romania).
Practical information
- General public
- Free
- This event is internal
Organizer
- Transp-or
Contact
- Michel Bierlaire