A Branch-and-Cut Algorithm for Partition Coloring

作者：Frota Yuri; Maculan Nelson; Noronha Thiago F; Ribeiro Celso C^*

来源：Networks, 2010, 55(3): 194-204.

DOI：10.1002/net.20365

• partition coloring
• branch and cut
• formulation by representatives

Let G = (V, E, Q) be a undirected graph, where V is the set of vertices, E is the set of edges, and Q = {Q(1),...,Q(q)} is a partition of V into q subsets. We refer to Q(1),...,Q(q) as the components of the partition. The partition coloring problem (PCP) consists of finding a subset V' of V with exactly one vertex from each component Q(1),...,Q(q) and such that the chromatic number of the graph induced in G by V' is minimum. This problem is a generalization of the graph coloring problem. This work presents a branch-and-cut algorithm proposed for PCP. An integer programing formulation and valid inequalities are proposed. A tabu search heuristic is used for providing primal bounds. Computational experiments are reported for random graphs and for PCP instances originating from the problem of routing and wavelength assignment in all-optical WDM networks.

• 出版日期2010-5