[pt] Esta tese faz um estudo do problema do Conjunto Dominante, um problema NP-difícil de grande relevância em aplicações relacionadas ao projeto de rede sem fio, mineração de dados, teoria de códigos, dentre outras. O conjunto dominante mínimo em um grafo é um conjunto mínimo de vértices de modo que cada vértice do grafo pertence a este conjunto ou é adjacente a um vértice que pertence a ele. Três variantes do problema foram estudadas; primeiro, uma variante na qual considera pesos nos vértices, buscando um conjunto dominante com menor peso total; segundo, uma variante onde o subgrafo induzido pelo conjunto dominante está conectado; e, finalmente, a variante que engloba essas duas características. Para resolver esses três problemas, propõe-se um algoritmo híbrido baseado na meta-heurística busca tabu com componentes adicionais de programação matemática, resultando em um método por vezes chamado de mateurística, (matheuristic, em inglês). Diversas técnicas adicionais e vizinhanças largas foram propostas
afim de alcançar regiões promissoras no espaço de busca. Análises experimentais demonstram a contribuição individual de todos esses componentes. Finalmente, o algoritmo é testado no problema do código de cobertura mínima, que pode ser visto como um caso especial do problema do conjunto dominante. Os códigos são estudados na métrica Hamming e na métrica Rosenbloom-Tsfasman. Neste último, diversos códigos menores foram encontrados. / [en] This thesis addresses the Dominating Set Problem, an NP- hard problem with great relevance in applications related to wireless network design, data mining, coding theory, among others. The minimum dominating set in a graph is a minimal set of vertices so that each vertex of the graph belongs to it or is adjacent to a vertex of this set. We study three variants of the problem: first, in the presence of weights on vertices, searching for a dominating set with smallest total weight; second, a variant where the subgraph induced by the dominating set needs to be connected, and,finally, the variant that encompasses these two characteristics. To solve these three problems, we propose a hybrid algorithm based on tabu search with additional mathematical-programming components, leading to a method sometimes called matheuristic. Several additional techniques and large neighborhoods are also employed to reach promising regions in the search space. Our experimental analyses show the good contribution of all these individual components. Finally, the algorithm is tested on the covering code problem, which can be viewed as a special case of the minimum dominating set problem. The codes are studied for the Hamming metric and the Rosenbloom-Tsfasman metric. For this last case, several shorter codes were found.
| Identifer | oai:union.ndltd.org:puc-rio.br/oai:MAXWELL.puc-rio.br:34169 |
| Date | 14 June 2018 |
| Creators | MAYRA CARVALHO ALBUQUERQUE |
| Contributors | THIBAUT VICTOR GASTON VIDAL |
| Publisher | MAXWELL |
| Source Sets | PUC Rio |
| Language | English |
| Detected Language | English |
| Type | TEXTO |
Page generated in 0.0024 seconds