Premium
A branch‐and‐cut algorithm for partition coloring
Author(s) -
Frota Yuri,
Maculan Nelson,
Noronha Thiago F.,
Ribeiro Celso C.
Publication year - 2010
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.20365
Subject(s) - combinatorics , mathematics , partition (number theory) , tabu search , vertex (graph theory) , graph partition , chromatic scale , graph coloring , discrete mathematics , graph , integer programming , algorithm
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. © 2009 Wiley Periodicals, Inc. NETWORKS, 2010