Título: Algoritmos Exatos para o Problema da Clique Máxima Ponderada.

Data: 06/04/2016 Horário: 08:30h Local: Sala de Seminários - Bloco 952

Resumo:

Neste trabalho, apresentamos três algoritmos enumerativos para o problema da clique máxima ponderada. Todos eles dependem de uma ordenação inicial dos vértices do grafos. Duas ordens são consideradas, em função dos pesos dos vértices ou dos pesos de seus vizinhos no grafo, levando a duas versões de cada algoritmo. O primeiro algoritmo, denominado BITCLIQUE, é um Branch & Bound combinatório. Ele combina de forma efetiva adaptações de várias ideias já empregadas com sucesso para resolver o problema, como a ação de uma heurística de coloração ponderada inteira, para definir limites superiores assim como regras de poda e ramificação, e o uso de vetores de bits, como estrutura de dados para simplificar operações sobre o grafo. O algoritmo proposto supera os algoritmos de Branch & Bound do estado da arte na maior parte das instâncias analisadas tanto na quantidade de subproblemas enumerados quanto no tempo de computação demandado. O segundo é um algoritmo de Bonecas Russas, denominado BITRDS, que incorpora ao método uma estratégia de poda e ramificação baseada em coloração ponderada. Testes computacionais demonstram que BITRDS reduz a quantidade o número de subproblemas quando o tempo de execução quando comparado com o melhor algoritmo de Bonecas Russas para o problema em instâncias aleatórias com densidade superior 50%. Essa diferença cresce à medida que a densidade do grado aumenta. Além disso, BITRDS mostra-se competitivo com BITCLIQUE, obtendo melhor desempenho em instâncias aleatórias com densidade entre 50% e 80%. Por último, apresentamos uma cooperação entre o método de Bonecas Russas e o método de Busca por Resolução. O algoritmo proposto, denominado BITBR, utiliza tanto a coloração ponderada quanto o limite superior dado pelas bonecas para encontrar um nogood. O algoritmo híbrido reduz o número de chamadas à heurística de coloração, chegando até 1 ordem de magnitude, quando comparamos com BITRDS. Porém, essa redução diminui o tempo de execução apenas em poucas instâncias. Diversos experimentos computacionais são realizados com os algoritmos propostos e os principais algoritmos do estado da arte. Resultados computacionais são apresentados para cada algoritmo utilizando as principais instâncias disponíveis na literatura. Finalmente, futuras direções de pesquisas são discutidas.

Banca:

• Prof. Dr. Manoel Bezerra Campelo Neto (UFC - Orientador)
• Prof. Dr. Philippe Michelon (Univ-Avignon - Orientador - Cotutela)
• Prof. Dr. Carlos Diego Rodrigues (DEMA/UFC - Coorientador)
• Prof. Dr. Thierry Mautor (UVSQ)
• Prof. Dr. Haroldo Gambini Santos (UFOP)
• Prof. Dr. Ricardo Cordeiro Correa (UFRRJ)
• Prof. Dr. Rudini Menezes Sampaio (UFC)