Lower Bounds and a Tabu Search Algorithm for the Minimum Deficiency Problem

, , and

BibTeX reference

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.

, 27 pages

Research Axis

Research application


Lower bounds and a Tabu search algorithm for the minimum deficiency problem
, , and
Journal of Combinatorial Optimization, 17(2), 168–191, 2009 BibTeX reference