Advanced search options

Advanced Search Options 🞨

Browse by author name (“Author name starts with…”).

Find ETDs with:

in
/  
in
/  
in
/  
in

Written in Published in Earliest date Latest date

Sorted by

Results per page:

You searched for id:"oai:MAXWELL.puc-rio.br:34169". One record found.

Search Limiters

Last 2 Years | English Only

No search limiters apply to these results.

▼ Search Limiters


Pontifical Catholic University of Rio de Janeiro

1. MAYRA CARVALHO ALBUQUERQUE. [en] MATHEURISTICS FOR VARIANTS OF THE DOMINATING SET PROBLEM.

Degree: 2018, Pontifical Catholic University of Rio de Janeiro

[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.

Advisors/Committee Members: THIBAUT VICTOR GASTON VIDAL.

Subjects/Keywords: [pt] BUSCA TABU; [en] TABU SEARCH; [pt] CONJUNTO DOMINANTE; [en] DOMINATING SET; [pt] CODIGO DE COBERTURA; [en] COVERING CODE; [pt] MATEURISTICAS; [en] MATHEURISTICS; [pt] BUSCA EM VIZINHANCA LARGA; [en] NEIGHBORHOOD SEARCH

Record DetailsSimilar RecordsGoogle PlusoneFacebookTwitterCiteULikeMendeleyreddit

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6th Edition):

ALBUQUERQUE, M. C. (2018). [en] MATHEURISTICS FOR VARIANTS OF THE DOMINATING SET PROBLEM. (Thesis). Pontifical Catholic University of Rio de Janeiro. Retrieved from http://www.maxwell.vrac.puc-rio.br/Busca_etds.php?strSecao=resultado&nrSeq=34169

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Chicago Manual of Style (16th Edition):

ALBUQUERQUE, MAYRA CARVALHO. “[en] MATHEURISTICS FOR VARIANTS OF THE DOMINATING SET PROBLEM.” 2018. Thesis, Pontifical Catholic University of Rio de Janeiro. Accessed September 26, 2018. http://www.maxwell.vrac.puc-rio.br/Busca_etds.php?strSecao=resultado&nrSeq=34169.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

MLA Handbook (7th Edition):

ALBUQUERQUE, MAYRA CARVALHO. “[en] MATHEURISTICS FOR VARIANTS OF THE DOMINATING SET PROBLEM.” 2018. Web. 26 Sep 2018.

Vancouver:

ALBUQUERQUE MC. [en] MATHEURISTICS FOR VARIANTS OF THE DOMINATING SET PROBLEM. [Internet] [Thesis]. Pontifical Catholic University of Rio de Janeiro; 2018. [cited 2018 Sep 26]. Available from: http://www.maxwell.vrac.puc-rio.br/Busca_etds.php?strSecao=resultado&nrSeq=34169.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Council of Science Editors:

ALBUQUERQUE MC. [en] MATHEURISTICS FOR VARIANTS OF THE DOMINATING SET PROBLEM. [Thesis]. Pontifical Catholic University of Rio de Janeiro; 2018. Available from: http://www.maxwell.vrac.puc-rio.br/Busca_etds.php?strSecao=resultado&nrSeq=34169

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

.