An effective heuristic algorithm for sum coloring of graphs

An effective heuristic algorithm for sum coloring of graphs

0.00 Avg rating0 Votes
Article ID: iaor201111461
Volume: 39
Issue: 7
Start Page Number: 1593
End Page Number: 1600
Publication Date: Jul 2012
Journal: Computers and Operations Research
Authors: ,
Keywords: heuristics
Abstract:

Given an undirected graph G = ( V , E ) equ1, the minimum sum coloring problem (MSCP) is to find a legal vertex coloring of G, using colors represented by natural numbers ( 1,2 , ) equ2 such that the total sum of the colors assigned to the vertices is minimized. In this paper, we present EXSCOL, a heuristic algorithm based on independent set extraction for this NP‐hard problem. EXSCOL identifies iteratively collections of disjoint independent sets of equal size and assign to each independent set the smallest available color. For the purpose of computing large independent sets, EXSCOL employs a tabu search based heuristic. Experimental evaluations on a collection of 52 DIMACS and COLOR2 benchmark graphs show that the proposed approach achieves highly competitive results. For more than half of the graphs used in the literature, our approach improves the current best known upper bounds.

Reviews

Required fields are marked *. Your email address will not be published.