Groupe d’études et de recherche en analyse des décisions

G-2007-69

On a Reduction of the Interval Coloring Problem to a Series of Bandwidth Coloring Problems

, et

Given a graph with strictly positive integer weights on the vertices , an interval coloring of is a function that assigns an interval of consecutive integers (called colors) to each vertex so that for all edges . The interval coloring problem is to determine an interval coloring that uses as few colors as possible. Assuming that a strictly positive integer weight is associated with each edge , a bandwidth coloring of is a function that assigns an integer (called a color) to each vertex so that for all edges . The bandwidth coloring problem is to determine a bandwidth coloring with minimum difference between the largest and the smallest colors used. We prove that an optimal solution of the interval coloring problem can be obtained by solving a series of bandwidth coloring problems. Computational experiments demonstrate that such a reduction can help to solve larger instances or to obtain better upper bounds on the optimal solution value of the interval coloring problem.

, 23 pages