Lower bounds and a tabu search algorithm for the minimum deficiency problem

Lower bounds and a tabu search algorithm for the minimum deficiency problem

0.00 Avg rating0 Votes
Article ID: iaor200937826
Country: Netherlands
Volume: 17
Issue: 2
Start Page Number: 168
End Page Number: 191
Publication Date: Feb 2009
Journal: Journal of Combinatorial Optimization
Authors: , ,
Keywords: heuristics: tabu search
Abstract:

An edge coloring of a graph G=(V,E) is a function c:E⇒ℕ that assigns a color c(e) to each edge eE such that c(e)≠c(e') whenever e and e' have a common endpoint. Denoting S v (G,c) the set of colors assigned to the edges incident to a vertex vV, and D v (G,c) the minimum number of integers which must be added to S v (G,c) to form an interval, the deficiency D(G,c) of an edge coloring c is defined as the sum Σ vV D v (G,c), and the span of c is the number of colors used in c. The problem of finding, for a given graph, an edge coloring with a minimum deficiency is NP-hard. We give new lower bounds on the minimum deficiency of an edge coloring and on the span of edge colorings with minimum deficiency. We also propose a tabu search algorithm to solve the minimum deficiency problem and report experiments on various graph instances, some of them having a known optimal deficiency.

Reviews

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