Um método guloso de simplificação para o problema da K-Dispersão discreta em grafos

Registro completo de metadados
MetadadosDescriçãoIdioma
Autor(es): dc.contributorSilva, André Renato Villela da-
Autor(es): dc.contributorRocha, Danilo Artigas da-
Autor(es): dc.contributorSilva, Maise Dantas da-
Autor(es): dc.creatorMenezes, Sandro André de-
Data de aceite: dc.date.accessioned2024-07-22T13:56:17Z-
Data de disponibilização: dc.date.available2024-07-22T13:56:17Z-
Data de envio: dc.date.issued2024-07-12-
Data de envio: dc.date.issued2024-07-12-
Fonte completa do material: dc.identifierhttps://app.uff.br/riuff/handle/1/33285-
Fonte: dc.identifier.urihttp://educapes.capes.gov.br/handle/capes/823333-
Descrição: dc.descriptionEste artigo descreve uma metodologia gulosa idealizada para buscar uma solução ótima para o problema da k-dispersão em grafos, bem como a implementação aplicada para este fim. A abordagem proposta consiste em aplicar uma poda inicial nas arestas de um grafo completo sem eliminar a solução ótima e realizar uma busca progressiva promovendo novas podas a cada k-clique candidata encontrada, de forma a reduzir o tamanho do problema. As sucessivas podas fazem o grafo reduzir de tamanho rapidamente, o que permite que grandes instâncias também sejam tratadas. Os tempos de execução foram comparados com os obtidos pelo algoritmo “branch-and- bound” por meio da execução do software CPLEX, que foi utilizado para confirmar a corretude dos resultados obtidos-
Descrição: dc.descriptionThis paper describes a greedy methodology idealized to seek an optimal solution to the problem of k-dispersion in graphs, as well as the implementation applied for this purpose. The proposed approach consists of applying an initial pruning to the edges of a complete graph without eliminating the optimal solution and performing a progressive search promoting new pruning for each k-clique candidate found, in order to reduce the size of the problem. Successive prunings causes the graph to reduce in size quickly, which allows large instances to be treated as well. The execution times were compared with those obtained by the “branch-and-bound” algorithm through the execution of the CPLEX software, which was used to confirm the correctness of the results obtained-
Descrição: dc.description21 p.-
Formato: dc.formatapplication/pdf-
Idioma: dc.languagept_BR-
Direitos: dc.rightsOpen Access-
Direitos: dc.rightsCC-BY-SA-
Palavras-chave: dc.subjectK-Dispersão-
Palavras-chave: dc.subjectProgramação Linear-
Palavras-chave: dc.subjectProgramação Inteira-
Palavras-chave: dc.subjectTópicos Teoria e Algoritmos em Grafos (TAG)-
Palavras-chave: dc.subjectOtimização Combinatória (OC)-
Palavras-chave: dc.subjectK-Dispersion-
Palavras-chave: dc.subjectLinear Programming-
Palavras-chave: dc.subjectInteger Programming-
Palavras-chave: dc.subjectPaper topics Graph Theory and Algorithms (GTA)-
Palavras-chave: dc.subjectCombinatorial Optimization (CO)-
Título: dc.titleUm método guloso de simplificação para o problema da K-Dispersão discreta em grafos-
Tipo de arquivo: dc.typeTrabalho de conclusão de curso-
Aparece nas coleções:Repositório Institucional da Universidade Federal Fluminense - RiUFF

Não existem arquivos associados a este item.