UMR CNRS 7253

Site Tools


en:mscp

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Next revision
Previous revision
Last revisionBoth sides next revision
en:mscp [2013/05/14 08:33] – created moukrimen:mscp [2013/09/21 23:26] moukrim
Line 1: Line 1:
-Upper and Lower Bounds for the Minimum Sum Coloring Problem +====== Upper and Lower Bounds for the Minimum Sum Coloring Problem ====== 
- +=== Description ===
-Description+
  
 In this work, we study upper and lower bounds of the Minimum Sum Coloring Problem (MSCP) from a uniform point of view. MSCP is a graph coloring problem whose goal is to minimize the sum of colors, where colors are represented by natural numbers. We propose calculating upper and lower bounds for MSCP using a single coloring algorithm: a Memetic Algorithm (MA) hybridizing a simple genetic algorithm with local search. Our lower bound is based on partitioning the original graph into cliques. In this context we define a new problem for obtaining this kind of general lower bound, namely Partition into Cliques for MSCP (PCMSCP), and prove its NPcompleteness. We test our algorithm and compare it with other algorithms In this work, we study upper and lower bounds of the Minimum Sum Coloring Problem (MSCP) from a uniform point of view. MSCP is a graph coloring problem whose goal is to minimize the sum of colors, where colors are represented by natural numbers. We propose calculating upper and lower bounds for MSCP using a single coloring algorithm: a Memetic Algorithm (MA) hybridizing a simple genetic algorithm with local search. Our lower bound is based on partitioning the original graph into cliques. In this context we define a new problem for obtaining this kind of general lower bound, namely Partition into Cliques for MSCP (PCMSCP), and prove its NPcompleteness. We test our algorithm and compare it with other algorithms
Line 7: Line 6:
  
  
-People involved +=== People involved === 
-Yu Li +Yu Li\\ 
-Corinne Lucet +Corinne Lucet\\ 
-Aziz Moukrim +Aziz Moukrim\\ 
-Kaoutar Sghiouer+Kaoutar Sghiouer\\
  
  
-References +=== References === 
-[1] Y. Li, C. Lucet, A. Moukrim, and K. Sghiouer. Greedy algorithms for the minimum sum coloring problem. In International Workshop: Logistics and transport, 2009. +[1] Y. Li, C. Lucet, A. Moukrim, and K. Sghiouer. Greedy algorithms for the minimum sum coloring problem. In International Workshop: Logistics and transport, 2009.\\ 
-[2] A. Moukrim, K. Sghiouer, C. Lucet, and Y. Li. Lower bounds for the minimum sum coloring problem. Electronic Notes in Discrete Mathematics, 36:663–670, 2010. +[2] A. Moukrim, K. Sghiouer, C. Lucet, and Y. Li. Lower bounds for the minimum sum coloring problem. Electronic Notes in Discrete Mathematics, 36:663–670, 2010.\\ 
-[3]A. Moukrim, K. Sghiouer, C. Lucet, and Y. Li. {{en:mscp_23_janvier_2013.pdf|Upper and Lower Bounds for the Minimum Sum Coloring Problem}}. Submitted, january 2013.+[3] A. Moukrim, K. Sghiouer, C. Lucet, and Y. Li. {{en:mscp_cor13septembre2013.pdf|Upper and Lower Bounds for the Minimum Sum Coloring Problem}}. Submitted, January 2013, revised September 2013.
  
  

User Tools