Please use this identifier to cite or link to this item:
http://repositorio.ufc.br/handle/riufc/69697| Type: | TCC |
| Title: | Hard instances for the maximum clique problem |
| Title in English: | Hard instances for the maximum clique problem |
| Authors: | David, Rodrigo Nogueira Lima |
| Advisor: | Campos, Victor Almeida |
| Keywords: | Teoria dos grafos;Clique máxima;Branch and bound;Coloração de grafos;Graph theory;Maximum clique;Graph coloring |
| Issue Date: | 2022 |
| Citation: | DAVID, Rodrigo Nogueira Lima. Hard instances for the maximum clique problem. 2022. 26 f. Monografia (Graduação em Ciência da Computação) - Universidade Federal do Ceará, Fortaleza, 2022. |
| Abstract in Brazilian Portuguese: | Uma clique em um grafo é um conjunto de vértices no qual todos são dois a dois adjacentes. O problema da Clique Máxima é um problema clássico de otimização em Teoria dos Grafos no qual deseja-se encontrar uma clique máxima em um grafo de entrada. Embora existam diversos resultados de dificuldade teórica sobre o problema, experimentos computacionais mostram que ele parece ser mais fácil do que o esperado. Neste trabalho, nós abordamos uma classe de algoritmos de Branch and Bound para o problema e como eles tornam Clique Máxima mais fácil na prática. Também, analisamos a correlação entre cliques e colorações e a diferença de dificuldade na enumeração dessas estruturas. Além disso, propomos instâncias cuja solução via enumeração é mais complexa em comparação com a média. Por fim, analisamos uma família de instâncias de pior caso para uma classe mais específica de algoritmos e propomos um pré-processamento que torna o tempo de solução dessas instâncias polinomial, além de uma construção não-determinística de grafos imunes a este pré-processamento. |
| Abstract: | A clique in a graph is a set of vertices in which all of its elements are pairwise adjacent. The Maximum Clique problem is a classic optimization problem in Graph Theory in which the objective is to find a maximum clique in a input graph G. Despite the existence of several theoretical hardness results for this problem, several experiments paint it as easier than one would expect. In this work, we approach a class of Branch and Bound algorithms for this problem, and how they make Maximum Clique often easier in practice. Furthermore, we analyze the correlation between cliques and colorings and the hardness difference in enumerating these structures. Besides that, we present instances whose solution via enumeration is more complex when compared to the average. Finally, we analyze a family of worst case instances for a more specific class of algorithms and propose a pre-processing that makes it possible for these instances to be solved in polynomial time, as well as a randomized construction that builds instances that are immune to this pre-processing. |
| URI: | http://www.repositorio.ufc.br/handle/riufc/69697 |
| Appears in Collections: | CIÊNCIA DA COMPUTAÇÃO - Monografias |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| 2022_tcc_rnldavid.pdf | 557,79 kB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.