G-2008-03
About Equivalent Interval Colorings of Weighted Graphs
, et référence BibTeX
Given a graph G=(V,E) with strictly positive integer weights
on the vertices
,
a k-interval coloring of G
is a function I that assigns an interval
of
consecutive integers (called colors)
to each vertex
. If two adjacent vertices x and y have
common colors, i.e.
for an edge
in G, then the edge
is said conflicting. A
k-interval coloring without conflicting edges is said legal.
The interval coloring problem (ICP) is to determine the smallest
integer k, called interval chromatic number of G and
denoted
, such that there exists a legal k-interval
coloring of G. For a fixed integer k, the k-interval graph
coloring problem (k-ICP) is to determine a k-interval coloring
of G with a minimum number of conflicting edges. The ICP and
k-ICP generalize classical vertex coloring problems where a
single color has to be assigned to each vertex (i.e.,
for all vertices
).
Two k-interval colorings I1 and I2 are said equivalent
if there is a permutation of the integers
such
that
if and only if
for all
vertices
. As for classical vertex coloring, the efficiency
of algorithms that solve the ICP or the k-ICP can be increased by
avoiding considering equivalent k-interval colorings. To this
purpose, we define and prove a necessary and sufficient condition
for the equivalence of two k-interval colorings. We then show how
a simple tabu search algorithm for the k-ICP can possibly be
improved by forbidding the visit of equivalent solutions.
Paru en janvier 2008 , 18 pages