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
Solving the Minimum Weighted Coloring Problem / Caramia, M.; Dell'Olmo, Paolo. - In: NETWORKS. - ISSN 0028-3045. - STAMPA. - 38 (2):(2001), pp. 88-101. [10.1002/net.1028]
Solving the Minimum Weighted Coloring Problem
DELL'OLMO, Paolo
2001
Abstract
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 algorithmI documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.