Algorithms for the minimum sum coloring problem: a review
---
paper_title: A one-to-one correspondence between potential solutions of the cluster deletion problem and the minimum sum coloring problem, and its application to P 4 -sparse graphs

paper_content:

In this note we show a one-to-one correspondence between potentially optimal solutions to the cluster deletion problem in a graph G and potentially optimal solutions for the minimum sum coloring problem in G ? (i.e. the complement graph of G). We apply this correspondence to polynomially solve the cluster deletion problem in a subclass of P 4 -sparse graphs that strictly includes P 4 -reducible graphs. We obtain a polynomial time algorithm for the cluster deletion for the family of P 4 -reducible graphs.We obtain a one-to-one correspondence between potentially optimal solutions to the cluster deletion (resp. minimum sum coloring) problem in a graph G (resp. G ? ).We apply such correspondence in order to solve the cluster deletion problem on almost all P 4 -sparse graphs.
---
paper_title: On a graph partition problem with application to VLSI layout

paper_content:

We discuss a graph partition problem with application to VLSI layout. It is not difficult to show that the general partition problem is NPComplete, so we restrict our attention to some special classes of graphs. A graph is called a circZe graph if the nodes of the graph represent the chords of a circle and there is an edge between the two nodes if the corresponding chords intersect. Supowit in [17] had posed the partition problem of circle graphs as an open problem. However, it is also not too difficult to show that the partition problem on circle graphs remains NP-Complete. We give an integer linear programming formulation for the general graph par-
---
paper_title: Approximation Algorithms for the Chromatic Sum

paper_content:

The chromatic sum of a graph G is the smallest total among all proper colorings of G using natural numbers. It was shown that computing the chromatic sum is NP-hard. In this article we prove that a simple greedy algorithm applied to sparse graphs gives a "good" approximation of the chromatic sum. For all graphs the existence of a polynomial time algorithm that approximates the chromatic sum with a linear function error implies P = NP.
---
paper_title: A tabu search approach for the sum coloring problem

paper_content:

Abstract The sum coloring problem has many applications in scheduling. It is a variant of the vertex coloring problem where the objective is to minimize the sum of colors used in coloring the vertices. In this paper, we use tabu search to solve the sum coloring problem. Experiments are performed on instances extracted from the second DIMACS challenge. Results show significative improvements on some chromatic sum bounds.
---
paper_title: Sum List Coloring Graphs

paper_content:

Let G=(V,E) be a graph with n vertices and e edges. The sum choice number of G is the smallest integer p such that there exist list sizes (f(v):v ∈ V) whose sum is p for which G has a proper coloring no matter which color lists of size f(v) are assigned to the vertices v. The sum choice number is bounded above by n+e. If the sum choice number of G equals n+e, then G is sum choice greedy. Complete graphs Kn are sum choice greedy as are trees. Based on a simple, but powerful, lemma we show that a graph each of whose blocks is sum choice greedy is also sum choice greedy. We also determine the sum choice number of K2,n, and we show that every tree on n vertices can be obtained from Kn by consecutively deleting single edges where all intermediate graphs are sc-greedy.
---
paper_title: Finding a Maximum Planar Subset of a Set of Nets in a Channel

paper_content:

An algorithm is presented that, given N two-pin nets in a channel, finds, in O(N/sup 2/) time, the largest subset that can be routed all on one layer
---
paper_title: Special issue on computational methods for graph coloring and its generalizations

paper_content:

A system for controlling the idling engine speed (output) of an internal combustion engine (controlled device) in an automotive vehicle in either open-loop or feedback control mode is disclosed. In the open-loop control mode, the control operation is based on the cooling water temperature of the engine, in the feedback control mode, the control operation being based on the deviation of an actual engine speed from the reference (input) engine speed. In some conventional systems, there is provided a time delay between the transfer of control from open-loop control to feedback control. However, according to the present invention there is provided a means for supplying instantaneously an additional intake air flow quantity to the engine in addition to the intake air quantity required in the feedback control mode at the instant when the control mode is transferred from the open-loop to feedback control. Consequently, the engine speed gradually settles at the reference engine speed without unfavorable hunting and overshooting so that an engine stalling due to lowered reference engine speed can be prevented.
---
paper_title: Lower Bounds for the Minimal Sum Coloring Problem

paper_content:

Abstract In this paper we present our study of the minimum sum coloring problem (MSCP). We propose a general lower bound for MSCP based on extraction of specific partial graphs. Also, we propose a lower bound using some decomposition into cliques. The experimental results show that our approach improves the results for most literature instances.
---
paper_title: The chromatic sum of a graph: history and recent developments

paper_content:

The chromatic sum of a graph is the ::: smallest sum of colors among all proper colorings with natural ::: numbers. The strength of a graph is the minimum number ::: of colors necessary to obtain its chromatic sum. A natural ::: generalization of chromatic sum is optimum cost chromatic ::: partition (OCCP) problem, where the costs of colors can be ::: arbitrary positive numbers. Existing results about chromatic sum, ::: strength of a graph, and OCCP problem are presented together with ::: some recent developments. The focus is on polynomial algorithms ::: for some families of graphs and NP-completeness issues.
---
paper_title: Greedy Algorithms for the Minimum Sum Coloring Problem

paper_content:

Greedy algorithms play an important role in the practical resolution of NP-hard problems. A greedy algorithm is a basic heuristic that builds a solution by iteratively adding the locally best element into the solution according to certain criteria. A greedy algorithm can either be used on its own to obtain a “good” solution, or it can be integrated into global optimization methods, for example, to limit the search space in branch and bound algorithms, or to generate initial solutions in metaheuristics. In this paper we are interested in greedy algorithms for the Minimum Sum Coloring Problem (MSCP). Since MSCP is closely related to the basic Graph Coloring Problem (GCP), we start our study with GCP and then turn to MSCP. Concerning GCP, although a lot of work has been reported in the literature, little of it concerns greedy algorithms. The most widely used greedy algorithms remain DSATUR and
---
paper_title: Solving the minimum sum coloring problem via binary quadratic programming

paper_content:

In recent years, binary quadratic programming (BQP) has been successively applied to solve several combinatorial optimization problems. We consider in this paper a study of using the BQP model to solve the minimum sum coloring problem (MSCP). For this purpose, we recast the MSCP with a quadratic model which is then solved via a recently proposed Path Relinking (PR) algorithm designed for the general BQP. Based on a set of MSCP benchmark instances, we investigate the performance of this solution approach compared with existing methods.
---
paper_title: K.: On sum coloring of graphs with parallel genetic algorithms

paper_content:

Chromatic number, chromatic sum and chromatic sum number are important graph coloring characteristics. The paper proves that a parallel metaheuristic like the parallel genetic algorithm (PGA) can be efficiently used for computing approximate sum colorings and finding upper bounds for chromatic sums and chromatic sum numbers for hard---to---color graphs. Suboptimal sum coloring with PGA gives usually much closer upper bounds then theoretical formulas known from the literature.
---
paper_title: Hybrid evolutionary search for the minimum sum coloring problem of graphs

paper_content:

Given a graph G, a proper k-coloring of G is an assignment of k colors { 1 , ? , k } to the vertices of G such that two adjacent vertices receive two different colors. The minimum sum coloring problem (MSCP) is to find a proper k-coloring while minimizing the sum of the colors assigned to the vertices. This paper presents a stochastic hybrid evolutionary search algorithm for computing upper and lower bounds of this NP-hard problem. The proposed algorithm relies on a joint use of two dedicated crossover operators to generate offspring solutions and an iterated double-phase tabu search procedure to improve offspring solutions. A distance-and-quality updating rule is used to maintain a healthy diversity of the population. We show extensive experimental results to demonstrate the effectiveness of the proposed algorithm and provide the first landscape analysis of MSCP to shed light on the behavior of the algorithm.
---
paper_title: A study of Breakout Local Search for the minimum sum coloring problem

paper_content:

Given an undirected graph G=(V,E), the minimum sum coloring problem (MSCP) is to find a legal assignment of colors (represented by natural numbers) to each vertex of G such that the total sum of the colors assigned to the vertices is minimized. In this paper, we present Breakout Local Search (BLS) for MSCP which combines some essential features of several well-established metaheuristics. BLS explores the search space by a joint use of local search and adaptive perturbation strategies. Tested on 27 commonly used benchmark instances, our algorithm shows competitive performance with respect to recently proposed heuristics and is able to find new record-breaking results for 4 instances.
---
paper_title: A local search heuristic for chromatic sum

paper_content:

A coloring of an undirected graph is a labelling of the vertices in the graph such that no two adjacent vertices receive the same label. The sum coloring problem asks to find a coloring, using natural numbers as labels, such that the total sum of the colors used is minimized. We design and test a local search algorithm, based on variable neighborhood search and iterated local search, that outperforms in several instances the currently existing benchmarks on this problem.
---
paper_title: A memetic algorithm for the minimum sum coloring problem

paper_content:

Given an undirected graph $G$, the Minimum Sum Coloring problem (MSCP) is to find a legal assignment of colors (represented by natural numbers) to each vertex of $G$ such that the total sum of the colors assigned to the vertices is minimized. This paper presents a memetic algorithm for MSCP based on a tabu search procedure with two neighborhoods and a multi-parent crossover operator. Experiments on a set of 77 well-known DIMACS and COLOR 2002-2004 benchmark instances show that the proposed algorithm achieves highly competitive results in comparison with five state-of-the-art algorithms. In particular, the proposed algorithm can improve the best known results for 17 instances. We also provide upper bounds for 18 additional instances for the first time.
---
paper_title: New Algorithm for the Sum Coloring Problem

paper_content:

In this paper we are interested in the elaboration of an approached solution to the sum coloring problem (MSCP), which is an NP-hard problem derived from the graphs coloring (GCP). The problem (MSCP) consists in minimizing the sum of colors in a graph. Our resolution approach is based on an hybridization of a genetic algorithm and a local heuristic based on an improvement of the maximal independent set algorithm given by F.Glover [4].
---
paper_title: A New Ant Colony Optimization Algorithm for the Lower Bound of Sum Coloring Problem

paper_content:

We consider an undirected graph G?=?(V, E), the minimum sum coloring problem (MSCP) asks to find a valid vertex coloring of G, using natural numbers (1,2,...), the aim is to minimize the total sum of colors. In this paper we are interested in the elaboration of an approximate solution for the minimum sum coloring problem (MSCP), more exactly we try to give a lower bound for MSCP by looking for a decomposition of the graph based on the metaheuristic of ant colony optimization (ACO). We test different instances to validate our approach.
---
paper_title: On a graph partition problem with application to VLSI layout

paper_content:

We discuss a graph partition problem with application to VLSI layout. It is not difficult to show that the general partition problem is NPComplete, so we restrict our attention to some special classes of graphs. A graph is called a circZe graph if the nodes of the graph represent the chords of a circle and there is an edge between the two nodes if the corresponding chords intersect. Supowit in [17] had posed the partition problem of circle graphs as an open problem. However, it is also not too difficult to show that the partition problem on circle graphs remains NP-Complete. We give an integer linear programming formulation for the general graph par-
---
paper_title: Solving the minimum sum coloring problem via binary quadratic programming

paper_content:

In recent years, binary quadratic programming (BQP) has been successively applied to solve several combinatorial optimization problems. We consider in this paper a study of using the BQP model to solve the minimum sum coloring problem (MSCP). For this purpose, we recast the MSCP with a quadratic model which is then solved via a recently proposed Path Relinking (PR) algorithm designed for the general BQP. Based on a set of MSCP benchmark instances, we investigate the performance of this solution approach compared with existing methods.
---
paper_title: Hybrid evolutionary search for the minimum sum coloring problem of graphs

paper_content:

Given a graph G, a proper k-coloring of G is an assignment of k colors { 1 , ? , k } to the vertices of G such that two adjacent vertices receive two different colors. The minimum sum coloring problem (MSCP) is to find a proper k-coloring while minimizing the sum of the colors assigned to the vertices. This paper presents a stochastic hybrid evolutionary search algorithm for computing upper and lower bounds of this NP-hard problem. The proposed algorithm relies on a joint use of two dedicated crossover operators to generate offspring solutions and an iterated double-phase tabu search procedure to improve offspring solutions. A distance-and-quality updating rule is used to maintain a healthy diversity of the population. We show extensive experimental results to demonstrate the effectiveness of the proposed algorithm and provide the first landscape analysis of MSCP to shed light on the behavior of the algorithm.
---
paper_title: On Sum Coloring of Graphs

paper_content:

The sum coloring problem asks to find a vertex coloring of a given graph G, using natural numbers, such that the total sum of the colors is minimized. A coloring which achieves this total sum is called an optimum coloring and the minimum number of colors needed in any optimum coloring of a graph is called the strength of the graph. We prove the NP-hardness of finding the vertex strength for graphs with Δ = 6. Polynomial time algorithms are presented for the sum coloring of chain bipartite graphs and k-split graphs. The edge sum coloring problem and the edge strength of a graph are defined similarly. We prove that the edge sum coloring and the edge strength problems are both NP-complete for k-regular graphs, k ≥ 3. Also we give a polynomial time algorithm to solve the edge sum coloring problem on trees.
---
paper_title: A one-to-one correspondence between potential solutions of the cluster deletion problem and the minimum sum coloring problem, and its application to P 4 -sparse graphs

paper_content:

In this note we show a one-to-one correspondence between potentially optimal solutions to the cluster deletion problem in a graph G and potentially optimal solutions for the minimum sum coloring problem in G ? (i.e. the complement graph of G). We apply this correspondence to polynomially solve the cluster deletion problem in a subclass of P 4 -sparse graphs that strictly includes P 4 -reducible graphs. We obtain a polynomial time algorithm for the cluster deletion for the family of P 4 -reducible graphs.We obtain a one-to-one correspondence between potentially optimal solutions to the cluster deletion (resp. minimum sum coloring) problem in a graph G (resp. G ? ).We apply such correspondence in order to solve the cluster deletion problem on almost all P 4 -sparse graphs.
---
paper_title: Minimum Color Sum of Bipartite Graphs

paper_content:

The problem ofminimum color sumof a graph is to color the vertices of the graph such that the sum (average) of all assigned colors is minimum. Recently it was shown that in general graphs this problem cannot be approximated withinn1??, for any ?0, unlessNP=ZPP(Bar-Noyet al., Information and Computation140(1998), 183?202). In the same paper, a 9/8-approximation algorithm was presented for bipartite graphs. The hardness question for this problem on bipartite graphs was left open. In this paper we show that the minimum color sum problem for bipartite graphs admits no polynomial approximation scheme, unlessP=NP. The proof is byL-reducing the problem of finding the maximum independent set in a graph whose maximum degree is four to this problem. This result indicates clearly that the minimum color sum problem is much harder than the traditional coloring problem, which is trivially solvable in bipartite graphs. As for the approximation ratio, we make a further step toward finding the precise threshold. We present a polynomial 10/9-approximation algorithm. Our algorithm uses a flow procedure in addition to the maximum independent set procedure used in previous solutions.
---
paper_title: An introduction to chromatic sums

paper_content:

We introduce the new concept of the chromatic sum of a graph G, the smallest possible total among all proper colorings of G using natural numbers. We show that computing the chromatic sum for arbitrary graphs is an NP-complete problem. Indeed, a polynomial algorithm for the chromatic sum would be easily modified to compute the chromatic number. Even for trees the chromatic sum is far from trivial. We construct a family of trees to demonstrate that for each k, some trees need k colors to achieve the minimum sum. In fact, we prove that our family gives the smallest trees with this property. Moreover, we show that asymptotically, for each value of k, almost all trees require more than k colors. Finally, we present a linear algorithm for computing the chromatic sum of an arbitrary tree.
---
paper_title: Solving the minimum sum coloring problem via binary quadratic programming

paper_content:

In recent years, binary quadratic programming (BQP) has been successively applied to solve several combinatorial optimization problems. We consider in this paper a study of using the BQP model to solve the minimum sum coloring problem (MSCP). For this purpose, we recast the MSCP with a quadratic model which is then solved via a recently proposed Path Relinking (PR) algorithm designed for the general BQP. Based on a set of MSCP benchmark instances, we investigate the performance of this solution approach compared with existing methods.
---
paper_title: Coloring of trees with minimum sum of colors

paper_content:

The chromatic sum of a graph is the smallest sum of colors among all proper colorings with natural numbers. The strength is the minimum number of colors needed to achieve the chromatic sum. We construct for each positive integer k a tree with strength k that has maximum degree only 2k - 2. The result is best possible. © 1999 John Wiley & Sons, Inc. J Graph Theory 32: 354–358, 1999
---
paper_title: A note on the strength and minimum color sum of bipartite graphs

paper_content:

The strength of a graph G is the smallest integer s such that there exists a minimum sum coloring of G using integers {1,...,s}, only. For bipartite graphs of maximum degree @D we show the following simple bound: s@?@?@D/2@?+1. As a consequence, there exists a quadratic time algorithm for determining the strength and minimum color sum of bipartite graphs of maximum degree @D@?4.
---
paper_title: On Sum Coloring and Sum Multi-Coloring for Restricted Families of Graphs

paper_content:

We consider the sum coloring (chromatic sum) problem and the sum multi-coloring problem for restricted families of graphs. In particular, we consider the graph classes of proper intersection graphs of axis-parallel rectangles, proper interval graphs, and unit disk graphs. All the above-mentioned graph classes belong to a more general graph class of (k+1)-clawfree graphs (respectively, for k=4,2,5). We prove that sum coloring is NP-hard for penny graphs and unit square graphs which implies NP-hardness for unit disk graphs and proper intersection graphs of axis-parallel rectangles. We show a 2-approximation algorithm for unit square graphs, with the assumption that the geometric representation of the graph is given. For sum multi-coloring, we confirm that the greedy first-fit coloring, after ordering vertices by their demands, achieves a k-approximation for the preemptive version of sum multi-coloring on (k+1)-clawfree graphs. Finally, we study priority algorithms as a model for greedy algorithms for the sum coloring problem and the sum multi-coloring problem. We show various inapproximation results under several natural input representations.
---
paper_title: Sum Coloring of Bipartite Graphs with Bounded Degree

paper_content:

Abstract ::: We consider the Chromatic Sum Problem on bipartite graphs which ::: appears to be much harder than the classical Chromatic Number Problem. We prove that the Chromatic Sum Problem is NP-complete on planar ::: bipartite graphs with $\Delta \leq 5$, but polynomial on bipartite graphs ::: with $\Delta \leq 3$, for which we construct an $O(n^{2})$-time algorithm. ::: Hence, we tighten the borderline of intractability for this problem on ::: bipartite graphs with bounded degree, namely: the case $\Delta =3$ is easy, $% ::: \Delta =5$ is hard. Moreover, we construct a $27/26$-approximation ::: algorithm for this problem thus improving the best known approximation ratio of ::: $10/9$.
---
paper_title: Greedy Algorithms for the Minimum Sum Coloring Problem

paper_content:

Greedy algorithms play an important role in the practical resolution of NP-hard problems. A greedy algorithm is a basic heuristic that builds a solution by iteratively adding the locally best element into the solution according to certain criteria. A greedy algorithm can either be used on its own to obtain a “good” solution, or it can be integrated into global optimization methods, for example, to limit the search space in branch and bound algorithms, or to generate initial solutions in metaheuristics. In this paper we are interested in greedy algorithms for the Minimum Sum Coloring Problem (MSCP). Since MSCP is closely related to the basic Graph Coloring Problem (GCP), we start our study with GCP and then turn to MSCP. Concerning GCP, although a lot of work has been reported in the literature, little of it concerns greedy algorithms. The most widely used greedy algorithms remain DSATUR and
---
paper_title: A memetic algorithm for the minimum sum coloring problem

paper_content:

Given an undirected graph $G$, the Minimum Sum Coloring problem (MSCP) is to find a legal assignment of colors (represented by natural numbers) to each vertex of $G$ such that the total sum of the colors assigned to the vertices is minimized. This paper presents a memetic algorithm for MSCP based on a tabu search procedure with two neighborhoods and a multi-parent crossover operator. Experiments on a set of 77 well-known DIMACS and COLOR 2002-2004 benchmark instances show that the proposed algorithm achieves highly competitive results in comparison with five state-of-the-art algorithms. In particular, the proposed algorithm can improve the best known results for 17 instances. We also provide upper bounds for 18 additional instances for the first time.
---
paper_title: A tabu search approach for the sum coloring problem

paper_content:

Abstract The sum coloring problem has many applications in scheduling. It is a variant of the vertex coloring problem where the objective is to minimize the sum of colors used in coloring the vertices. In this paper, we use tabu search to solve the sum coloring problem. Experiments are performed on instances extracted from the second DIMACS challenge. Results show significative improvements on some chromatic sum bounds.
---
paper_title: Hybrid Evolutionary Algorithms for Graph Coloring

paper_content:

A recent and very promising approach for combinatorial optimization is to embed local search into the framework of evolutionary algorithms. In this paper, we present such hybrid algorithms for the graph coloring problem. These algorithms combine a new class of highly specialized crossover operators and a well-known tabu search algorithm. Experiments of such a hybrid algorithm are carried out on large DIMACS Challenge benchmark graphs. Results prove very competitive with and even better than those of state-of-the-art algorithms. Analysis of the behavior of the algorithm sheds light on ways to further improvement.
---
paper_title: A study of Breakout Local Search for the minimum sum coloring problem

paper_content:

Given an undirected graph G=(V,E), the minimum sum coloring problem (MSCP) is to find a legal assignment of colors (represented by natural numbers) to each vertex of G such that the total sum of the colors assigned to the vertices is minimized. In this paper, we present Breakout Local Search (BLS) for MSCP which combines some essential features of several well-established metaheuristics. BLS explores the search space by a joint use of local search and adaptive perturbation strategies. Tested on 27 commonly used benchmark instances, our algorithm shows competitive performance with respect to recently proposed heuristics and is able to find new record-breaking results for 4 instances.
---
paper_title: Using tabu search techniques for graph coloring

paper_content:

Tabu search techniques are used for moving step by step towards the minimum value of a function. A tabu list of forbidden movements is updated during the iterations to avoid cycling and being trapped in local minima. Such techniques are adapted to graph coloring problems. We show that they provide almost optimal colorings of graphs having up to 1000 nodes and their efficiency is shown to be significantly superior to the famous simulated annealing.
---
paper_title: A local search heuristic for chromatic sum

paper_content:

A coloring of an undirected graph is a labelling of the vertices in the graph such that no two adjacent vertices receive the same label. The sum coloring problem asks to find a coloring, using natural numbers as labels, such that the total sum of the colors used is minimized. We design and test a local search algorithm, based on variable neighborhood search and iterated local search, that outperforms in several instances the currently existing benchmarks on this problem.
---
paper_title: Hybrid Evolutionary Algorithms for Graph Coloring

paper_content:

A recent and very promising approach for combinatorial optimization is to embed local search into the framework of evolutionary algorithms. In this paper, we present such hybrid algorithms for the graph coloring problem. These algorithms combine a new class of highly specialized crossover operators and a well-known tabu search algorithm. Experiments of such a hybrid algorithm are carried out on large DIMACS Challenge benchmark graphs. Results prove very competitive with and even better than those of state-of-the-art algorithms. Analysis of the behavior of the algorithm sheds light on ways to further improvement.
---
paper_title: Solving the minimum sum coloring problem via binary quadratic programming

paper_content:

In recent years, binary quadratic programming (BQP) has been successively applied to solve several combinatorial optimization problems. We consider in this paper a study of using the BQP model to solve the minimum sum coloring problem (MSCP). For this purpose, we recast the MSCP with a quadratic model which is then solved via a recently proposed Path Relinking (PR) algorithm designed for the general BQP. Based on a set of MSCP benchmark instances, we investigate the performance of this solution approach compared with existing methods.
---
paper_title: K.: On sum coloring of graphs with parallel genetic algorithms

paper_content:

Chromatic number, chromatic sum and chromatic sum number are important graph coloring characteristics. The paper proves that a parallel metaheuristic like the parallel genetic algorithm (PGA) can be efficiently used for computing approximate sum colorings and finding upper bounds for chromatic sums and chromatic sum numbers for hard---to---color graphs. Suboptimal sum coloring with PGA gives usually much closer upper bounds then theoretical formulas known from the literature.
---
paper_title: Hybrid evolutionary search for the minimum sum coloring problem of graphs

paper_content:

Given a graph G, a proper k-coloring of G is an assignment of k colors { 1 , ? , k } to the vertices of G such that two adjacent vertices receive two different colors. The minimum sum coloring problem (MSCP) is to find a proper k-coloring while minimizing the sum of the colors assigned to the vertices. This paper presents a stochastic hybrid evolutionary search algorithm for computing upper and lower bounds of this NP-hard problem. The proposed algorithm relies on a joint use of two dedicated crossover operators to generate offspring solutions and an iterated double-phase tabu search procedure to improve offspring solutions. A distance-and-quality updating rule is used to maintain a healthy diversity of the population. We show extensive experimental results to demonstrate the effectiveness of the proposed algorithm and provide the first landscape analysis of MSCP to shed light on the behavior of the algorithm.
---
paper_title: A memetic algorithm for the minimum sum coloring problem

paper_content:

Given an undirected graph $G$, the Minimum Sum Coloring problem (MSCP) is to find a legal assignment of colors (represented by natural numbers) to each vertex of $G$ such that the total sum of the colors assigned to the vertices is minimized. This paper presents a memetic algorithm for MSCP based on a tabu search procedure with two neighborhoods and a multi-parent crossover operator. Experiments on a set of 77 well-known DIMACS and COLOR 2002-2004 benchmark instances show that the proposed algorithm achieves highly competitive results in comparison with five state-of-the-art algorithms. In particular, the proposed algorithm can improve the best known results for 17 instances. We also provide upper bounds for 18 additional instances for the first time.
---
paper_title: Tight Bounds on the Chromatic Sum of a Connected Graph

paper_content:

The chromatic sum of a graph is introduced in the dissertation of Ewa Kubicka. It is the smallest possible total among all proper colorings of G using natural numbers. In this article we determine tight bounds on the chromatic sum of a connected graph with e edges,
---
paper_title: K.: On sum coloring of graphs with parallel genetic algorithms

paper_content:

Chromatic number, chromatic sum and chromatic sum number are important graph coloring characteristics. The paper proves that a parallel metaheuristic like the parallel genetic algorithm (PGA) can be efficiently used for computing approximate sum colorings and finding upper bounds for chromatic sums and chromatic sum numbers for hard---to---color graphs. Suboptimal sum coloring with PGA gives usually much closer upper bounds then theoretical formulas known from the literature.
---
paper_title: Lower Bounds for the Minimal Sum Coloring Problem

paper_content:

Abstract In this paper we present our study of the minimum sum coloring problem (MSCP). We propose a general lower bound for MSCP based on extraction of specific partial graphs. Also, we propose a lower bound using some decomposition into cliques. The experimental results show that our approach improves the results for most literature instances.
---
paper_title: Hybrid evolutionary search for the minimum sum coloring problem of graphs

paper_content:

Given a graph G, a proper k-coloring of G is an assignment of k colors { 1 , ? , k } to the vertices of G such that two adjacent vertices receive two different colors. The minimum sum coloring problem (MSCP) is to find a proper k-coloring while minimizing the sum of the colors assigned to the vertices. This paper presents a stochastic hybrid evolutionary search algorithm for computing upper and lower bounds of this NP-hard problem. The proposed algorithm relies on a joint use of two dedicated crossover operators to generate offspring solutions and an iterated double-phase tabu search procedure to improve offspring solutions. A distance-and-quality updating rule is used to maintain a healthy diversity of the population. We show extensive experimental results to demonstrate the effectiveness of the proposed algorithm and provide the first landscape analysis of MSCP to shed light on the behavior of the algorithm.
---
paper_title: Improved Lower Bounds for Sum Coloring via Clique Decomposition

paper_content:

Given an undirected graph $G = (V,E)$ with a set $V$ of vertices and a set $E$ of edges, the minimum sum coloring problem (MSCP) is to find a legal vertex coloring of $G$, using colors represented by natural numbers $1, 2, . . .$ such that the total sum of the colors assigned to the vertices is minimized. This paper describes an approach based on the decomposition of the original graph into disjoint cliques for computing lower bounds for the MSCP. Basically, the proposed approach identifies and removes at each extraction iteration a maximum number of cliques of the same size (the largest possible) from the graph. Computational experiments show that this approach is able to improve on the current best lower bounds for 14 benchmark instances, and to prove optimality for the first time for 4 instances. We also report lower bounds for 24 more instances for which no such bounds are available in the literature. These new lower bounds are useful to estimate the quality of the upper bounds obtained with various heuristic approaches.
---
paper_title: A local search heuristic for chromatic sum

paper_content:

A coloring of an undirected graph is a labelling of the vertices in the graph such that no two adjacent vertices receive the same label. The sum coloring problem asks to find a coloring, using natural numbers as labels, such that the total sum of the colors used is minimized. We design and test a local search algorithm, based on variable neighborhood search and iterated local search, that outperforms in several instances the currently existing benchmarks on this problem.
---
paper_title: Solving the minimum sum coloring problem via binary quadratic programming

paper_content:

In recent years, binary quadratic programming (BQP) has been successively applied to solve several combinatorial optimization problems. We consider in this paper a study of using the BQP model to solve the minimum sum coloring problem (MSCP). For this purpose, we recast the MSCP with a quadratic model which is then solved via a recently proposed Path Relinking (PR) algorithm designed for the general BQP. Based on a set of MSCP benchmark instances, we investigate the performance of this solution approach compared with existing methods.
---
paper_title: Hybrid evolutionary search for the minimum sum coloring problem of graphs

paper_content:

Given a graph G, a proper k-coloring of G is an assignment of k colors { 1 , ? , k } to the vertices of G such that two adjacent vertices receive two different colors. The minimum sum coloring problem (MSCP) is to find a proper k-coloring while minimizing the sum of the colors assigned to the vertices. This paper presents a stochastic hybrid evolutionary search algorithm for computing upper and lower bounds of this NP-hard problem. The proposed algorithm relies on a joint use of two dedicated crossover operators to generate offspring solutions and an iterated double-phase tabu search procedure to improve offspring solutions. A distance-and-quality updating rule is used to maintain a healthy diversity of the population. We show extensive experimental results to demonstrate the effectiveness of the proposed algorithm and provide the first landscape analysis of MSCP to shed light on the behavior of the algorithm.
---
paper_title: A study of Breakout Local Search for the minimum sum coloring problem

paper_content:

Given an undirected graph G=(V,E), the minimum sum coloring problem (MSCP) is to find a legal assignment of colors (represented by natural numbers) to each vertex of G such that the total sum of the colors assigned to the vertices is minimized. In this paper, we present Breakout Local Search (BLS) for MSCP which combines some essential features of several well-established metaheuristics. BLS explores the search space by a joint use of local search and adaptive perturbation strategies. Tested on 27 commonly used benchmark instances, our algorithm shows competitive performance with respect to recently proposed heuristics and is able to find new record-breaking results for 4 instances.
---
paper_title: A memetic algorithm for the minimum sum coloring problem

paper_content:

Given an undirected graph $G$, the Minimum Sum Coloring problem (MSCP) is to find a legal assignment of colors (represented by natural numbers) to each vertex of $G$ such that the total sum of the colors assigned to the vertices is minimized. This paper presents a memetic algorithm for MSCP based on a tabu search procedure with two neighborhoods and a multi-parent crossover operator. Experiments on a set of 77 well-known DIMACS and COLOR 2002-2004 benchmark instances show that the proposed algorithm achieves highly competitive results in comparison with five state-of-the-art algorithms. In particular, the proposed algorithm can improve the best known results for 17 instances. We also provide upper bounds for 18 additional instances for the first time.
---
paper_title: Solving the minimum sum coloring problem via binary quadratic programming

paper_content:

In recent years, binary quadratic programming (BQP) has been successively applied to solve several combinatorial optimization problems. We consider in this paper a study of using the BQP model to solve the minimum sum coloring problem (MSCP). For this purpose, we recast the MSCP with a quadratic model which is then solved via a recently proposed Path Relinking (PR) algorithm designed for the general BQP. Based on a set of MSCP benchmark instances, we investigate the performance of this solution approach compared with existing methods.
---
paper_title: A local search heuristic for chromatic sum

paper_content:

A coloring of an undirected graph is a labelling of the vertices in the graph such that no two adjacent vertices receive the same label. The sum coloring problem asks to find a coloring, using natural numbers as labels, such that the total sum of the colors used is minimized. We design and test a local search algorithm, based on variable neighborhood search and iterated local search, that outperforms in several instances the currently existing benchmarks on this problem.
---
paper_title: A memetic algorithm for the minimum sum coloring problem

paper_content:

Given an undirected graph $G$, the Minimum Sum Coloring problem (MSCP) is to find a legal assignment of colors (represented by natural numbers) to each vertex of $G$ such that the total sum of the colors assigned to the vertices is minimized. This paper presents a memetic algorithm for MSCP based on a tabu search procedure with two neighborhoods and a multi-parent crossover operator. Experiments on a set of 77 well-known DIMACS and COLOR 2002-2004 benchmark instances show that the proposed algorithm achieves highly competitive results in comparison with five state-of-the-art algorithms. In particular, the proposed algorithm can improve the best known results for 17 instances. We also provide upper bounds for 18 additional instances for the first time.
---

Title: Algorithms for the Minimum Sum Coloring Problem: A Review

Section 1: Definitions and formulation of MSCP
Description 1: This section introduces the basic definitions and mathematical formulation of the Minimum Sum Coloring Problem (MSCP), including its objective and related graph theoretical concepts.

Section 2: Polynomial-time and k-approximation algorithms for MSCP
Description 2: This section reviews various polynomial-time and k-approximation algorithms that have been developed for specific classes of graphs and highlights their main characteristics and effectiveness.

Section 3: Heuristics and metaheuristics for MSCP
Description 3: This section provides a comprehensive review of heuristic and metaheuristic algorithms proposed for MSCP, categorizing them into greedy algorithms, local search heuristics, and evolutionary algorithms, and discussing their key ingredients and performance.

Section 4: Greedy algorithms
Description 4: This section delves into the details of various greedy algorithms developed for MSCP, discussing their methodologies and how they are used to generate initial solutions for other more complex algorithms.

Section 5: Local search heuristics
Description 5: This section examines local search heuristics, describing different neighborhood structures and transformation operators used to improve solutions, and categorizing them into single and multi-neighborhood searches.

Section 6: Evolutionary algorithms
Description 6: This section discusses evolutionary algorithms and their hybrid variants, focusing on memetic algorithms that combine genetic operators with local search improvements.

Section 7: Bounds for MSCP
Description 7: This section introduces theoretical and computational bounds of MSCP, explaining how they are derived and their significance in the context of evaluating the performance of different algorithms.

Section 8: Benchmark and performance evaluation
Description 8: This section introduces common benchmark instances used for assessing MSCP algorithms and summarizes the performance of the reviewed algorithms based on these benchmarks.

Section 9: Perspectives and conclusion
Description 9: This section discusses future research directions and concludes the review, emphasizing the importance of MSCP and possible advancements in solution methodologies.