Seminário de Teoria da Computação Um Algoritmo Branch-and-Cut para o problema de coloração particionada Yuri Abitbol de Menezes Frota Sexta-feira, 5 de dezembro de 2008 Sala 85 16:00hs Resumo: Let G=(V,E,Q) be a non-directed graph, where V is the set of nodes, E is the set of edges, and Q = {Q_1,Q_2,...,Q_q} is a partition of V into q subsets. We refer to Q_1,Q_2,...,Q_q as the components of the partition. The Partition Coloring Problem (PCP) consists in finding a subset V' of V with exactly one node from each component Q_1, Q_2,...,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 programming 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.