Título: Problema da Clique Máxima Ponderada

Data: 26/01/2015 Horário: 14h Local: Sala de Seminários Bloco 952

Resumo: O problema da clique máxima (MCP) consiste em encontrar um subgrafo completo (clique) de cardinalidade máxima. Uma importante generalização do problema da clique máxima é a sua versão ponderada nos vértices. Dado um grafo G = (V,E) e uma função de ponderação que associa a cada vértice v um valor positivo, o peso da clique é dado pelo somatório dos pesos dos vértices da clique. Logo, o problema da clique máxima ponderada consiste em encontrar uma clique com o peso máximo. O problema da clique máxima ponderada (MWCP) tem um extenso número de aplicações práticas em diversas áreas:
Bioinformática e Computação Biológia, Visão Computacional e Robótica. Além de sua relevância prática, MWCP é equivalente a outros problemas centrais de otimização combinatória em grafos como o problema do conjunto independente máximo ponderado e a cobertura ponderada mínima de vértices. Além disso, muitos problemas podem ser formulados diretamente como um problema de clique máxima ponderada ou tem um subproblema que requer  encontrar uma clique ponderada máxima. Recentes melhorias para o problema da clique máxima, como: ordem inicial apropriada dos vértices adequada; uso de heurística de coloração como regra de ramificação e procedimento de limite superior e operações baseada em paralelismo de bits encorajam o desenvolvimento de novos algoritmos para clique máxima ponderada. Mais recentemente, outras melhorias foram propostas relacionadas com o método de busca das bonecas russas permitindo que cada subproblema seja resolvido pelo método da boneca russa e a redução o número de bonecas enumeradas através de uma regra de eliminação. Esta proposta de doutorado tem como objetivo apresentar algoritmos exatos eficientes para encontrar clique máxima ponderada em grafos arbitrários. Os algoritmos não serão especializados para nenhum tipo particular de grafos. Os métodos utilizados serão: Branch-and-Bound, Método de busca das Bonecas Russas (Russian Dolls Search) e Busca por resolução (Resolution Search).

Banca:

• Manoel Bezerra Campêlo Neto  (UFC - Orientador)
• Carlos Diego Rodrigues (UFC)
• Phillippe Michelon  (Université d'Avignon et des Pays de Vaucluse, UNIV-AVIGNON, França)
• Thierry Mautor (Université de Versailles Saint Quentin)