Name
Abstract | ||
|---|---|---|
Abstract The minimum sum coloring problem ( M S C P ) is a vertex coloring problem in which a weight is associated with each color. Its aim is to find a coloring of the vertices of a graph G with the minimum sum of the weights of the used colors. The M S C P has important applications in the fields such as scheduling and VLSI design. The minimum number of colors among all optimal solutions of the M S C P for G is called the chromatic strength of G and is denoted by s ( G ) . A tight upper bound of s ( G ) allows to significantly reduce the search space when solving the M S C P . In this paper, we propose and empirically evaluate two new upper bounds of s ( G ) for general graphs, U B A and U B S , based on an abstraction of all possible colorings of G formulated as an ordered set of decreasing positive integer sequences. The experimental results on the standard benchmarks DIMACS and COLOR show that U B A is competitive, and that U B S is significantly tighter than those previously proposed in the literature for 70 graphs out of 74 and, in particular, reaches optimality for 8 graphs. Moreover, both U B A and U B S can be applied to the more general optimum cost chromatic partition ( O C C P ) problem. |
Year | Venue | Field |
|---|---|---|
2017 | Discrete Applied Mathematics | Complete coloring,Discrete mathematics,Edge coloring,Combinatorics,Vertex (geometry),Fractional coloring,Upper and lower bounds,Brooks' theorem,Greedy coloring,Partition (number theory),Mathematics |
DocType | Volume | Citations |
Journal | 233 | 0 |
PageRank | References | Authors |
0.34 | 20 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Clément Lecat | 1 | 1 | 0.69 |
| Corinne Lucet | 2 | 99 | 8.51 |
| Chu Min Li | 3 | 1194 | 85.65 |