Use este identificador para citar ou linkar para este item:
http://repositorio.ufc.br/handle/riufc/37248| Tipo: | Tese |
| Título: | Algoritmos exatos para problema da clique máxima ponderada |
| Título em inglês: | Exact algorithms for the maximum weighted clique problem |
| Autor(es): | Tavares, Wladimir Araújo |
| Orientador: | Campêlo Neto, Manoel Bezerra |
| Coorientador: | Michelon, Philippe |
| Palavras-chave: | Algoritmos exatos;Coloração de grafos;Paralelismo de bits;Bonecas russas;Busca por resolução |
| Data do documento: | 2016 |
| Citação: | 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. |
| 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. |
| 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 |
| Aparece nas coleções: | DCOMP - Teses defendidas na UFC |
Arquivos associados a este item:
| Arquivo | Descrição | Tamanho | Formato | |
|---|---|---|---|---|
| 2016_tese_watavares.pdf | 1,05 MB | Adobe PDF | Visualizar/Abrir |
Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.