G-2007-14
Lower Bounds and a Tabu Search Algorithm for the Minimum Deficiency Problem
, et référence BibTeX
An edge coloring of a graph
is a function
that assigns a color
to each edge
such that
whenever
and
have a common endpoint. Denoting
the set of colors assigned to the edges incident to a vertex
, and
the minimum number of integers which must be added to
to form an interval, the deficiency
of an edge coloring
is defined as the sum
, and the span of
is the number of colors used in
. 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.
Paru en mars 2007 , 27 pages