https://hal-u-picardie.archives-ouvertes.fr/hal-03636429Lecat, ClementClementLecatMIS - Modélisation, Information et Systèmes - UR UPJV 4290 - UPJV - Université de Picardie Jules VerneLucet, CorinneCorinneLucetMIS - Modélisation, Information et Systèmes - UR UPJV 4290 - UPJV - Université de Picardie Jules VerneLi, Chu-MinChu-MinLiCOALA - COntraintes, ALgorithmes et Applications - LIS - Laboratoire d'Informatique et Systèmes - AMU - Aix Marseille Université - UTLN - Université de Toulon - CNRS - Centre National de la Recherche ScientifiqueMIS - Modélisation, Information et Systèmes - UR UPJV 4290 - UPJV - Université de Picardie Jules VerneNew Lower Bound for the Minimum Sum Coloring ProblemHAL CCSD2017[INFO] Computer Science [cs]DESSAIVRE, Louise2022-04-10 11:39:242023-03-24 14:53:262022-04-10 11:39:24enConference papers1The Minimum Sum Coloring Problem (MSCP) is an NP-Hard problem derived from the graph coloring problem (GCP) and has practical applications in different domains such as VLSI design, distributed resource allocation, and scheduling. There exist few exact solutions for MSCP, probably due to its search space much more elusive than that of GCP. On the contrary, much effort is spent in the literature to develop upper and lower bounds for MSCP. In this paper, we borrow a notion called motif, that was used in a recent work for upper bounding the minimum number of colors in an optimal solution of MSCP, to develop a new algebraic lower bound called LBM Sigma for MSCP. Experiments on standard benchmarks for MSCP and GCP show that LBM Sigma is substantially better than the existing lower bounds for several families of graphs.