Premium
Solving the minimum‐weighted coloring problem
Author(s) -
Caramia Massimiliano,
Dell'Olmo Paolo
Publication year - 2001
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.1028
Subject(s) - heuristics , mathematics , combinatorics , generalization , vertex (graph theory) , fractional coloring , integer programming , benchmark (surveying) , reduction (mathematics) , upper and lower bounds , range (aeronautics) , discrete mathematics , mathematical optimization , graph , mathematical analysis , materials science , geometry , geodesy , line graph , graph power , composite material , geography
Weighted coloring is a generalization of the well‐known vertex (unweighted) coloring for which a number of exact algorithms have been presented in the literature. We are not aware of any optimal method specifically designed for the minimum‐weighted coloring problem on arbitrary graphs. Only a few heuristics have been developed with the goal of finding tighter upper bounds for the maximum‐weighted clique problem. Moreover, as shown in the paper, a straightforward reduction of a weighted instance into an unweighted one permits us to solve only very small instances. In this paper, we present a branch‐and‐bound algorithm for the weighted case capable of solving random graphs of up to 90 vertices for any edge density with integer weights uniformly drawn from the range [1, …,10]. Likewise, we have used properly modified benchmark instances borrowed from vertex coloring as a further test bed for our algorithm. © 2001 John Wiley & Sons, Inc.