Please use this identifier to cite or link to this item: http://www.repositorio.ufc.br/handle/riufc/37248
Title in Portuguese: Algoritmos exatos para problema da clique máxima ponderada
Title: Exact algorithms for the maximum weighted clique problem
Author: Tavares, Wladimir Araújo
Advisor(s): Campêlo Neto, Manoel Bezerra
Co-advisor(s): Michelon, Philippe
Keywords: Algoritmos exatos
Coloração de grafos
Paralelismo de bits
Bonecas Russas
Busca por resolução
Issue Date: 2016
Citation: TAVARES, Wladimir Araújo. Algoritmos exatos para problema da clique máxima ponderada. 2016. 182 f. Tese (Doutorado em Ciência da Computação)-Universidade Federal do Ceará, Fortaleza, 2016.
Abstract in Portuguese: 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.
Abstract: In this work, we present three new exact algorithms for the maximum weight clique problem. The three algorithms depend on an initial ordering of the vertices. Two ordering are considered, as a function of the weights of the vertices or the weights of the neighborhoods of the vertices. This leads to two versions of each algorithm. The first onde, called BITCLIQUE, is a combinatorial Branch & Bound algorithm. It effectively combines adaptations of several ideas already successfully employed to solve the problem, such as the use of a weighted integer coloring heuristic for pruning and branching, and the use of bitmap for simplifying the operations on the graph. The proposed algorithm outperforms state-of-the-art Branch & Bound algorithms in most instances of the considered in terms of the number of enumerated subproblems as well in terms of computational time. The second one is a Russian Dolls, called BITRDS, which incorporates the pruning and branching strategies based on weighted coloring. Computational tests show that BITRDS reduces both the number of enumerated subproblems and execution time when compared to the previous state-of-art Russian Dolls algorithm for the problem in random graph instances with density above 50%. As graph density increases, this difference increases. Besides, BITRDS is competitive with BITCLIQUE with better performance in random graph instances with density between 50% and 80%. Finally, we present a cooperation between the Russian Dolls method and the Resolution Search method. The proposed algorithm, called BITBR, uses both the weighted coloring and upper bounds given by the dolls to find a nogood. The hybrid algorithm reduces the number of coloring heuristic calls, reaching up to 1 order of magnitude when compared with BITRDS. However, this reduction decreases the execution time only in a few instances. Several computational experiments are carried out with the proposed and state-of-the-art algorithms. Computational results are reported for each algorithm using the main instances available in the literature. Finally, future directions of research are discussed.
URI: http://www.repositorio.ufc.br/handle/riufc/37248
Appears in Collections:DCOMP - Teses defendidas na UFC

Files in This Item:
File Description SizeFormat 
2016_tese_watavares.pdf1,05 MBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.