Um estudo de heurísticas para o problema da k-Dominação

Registro completo de metadados
MetadadosDescriçãoIdioma
Autor(es): dc.contributorSilva, Maise Dantas da-
Autor(es): dc.contributorhttp://lattes.cnpq.br/./2700813865300157-
Autor(es): dc.contributorMafort, Rodrigo Lamblet-
Autor(es): dc.contributorSilva, André Renato Villela da-
Autor(es): dc.contributorhttp://lattes.cnpq.br/./4345875813789026-
Autor(es): dc.contributorRocha, Danilo Artigas da-
Autor(es): dc.contributorhttp://lattes.cnpq.br/./2404542754757428-
Autor(es): dc.contributorAndrade, Marcos Ribeiro Quinet de-
Autor(es): dc.contributorhttp://lattes.cnpq.br/./8900303425878153-
Autor(es): dc.creatorRangel, Beatriz da Silva-
Data de aceite: dc.date.accessioned2024-07-11T17:45:18Z-
Data de disponibilização: dc.date.available2024-07-11T17:45:18Z-
Data de envio: dc.date.issued2023-01-02-
Data de envio: dc.date.issued2023-01-02-
Fonte completa do material: dc.identifierhttp://app.uff.br/riuff/handle/1/27476-
Fonte: dc.identifier.urihttp://educapes.capes.gov.br/handle/capes/756834-
Descrição: dc.descriptionO Problema da k-Dominação Mínima consiste em encontrar, para um grafo G = (V, E), um conjunto mínimo S ⊆ V de forma que cada vértice v ∈ V pertence a S ou possui pelo menos k vizinhos em S. Por se tratar de um problema NP-difícil, encontrar uma solução exata para este problema tende a ser custoso computacionalmente. Neste trabalho, são apresentadas seis heurísticas gulosas, que exploram os requisitos e os graus dos vértices, bem como combinações dos dois fatores. Os experimentos realizados foram divididos em duas etapas. A primeira consiste na comparação dos resultados das heurísticas com as soluções exatas, para grafos com vinte, cinquenta e cem vértices. Já na segunda etapa, que considera grafos com até dez mil vértices, as heurísticas são comparadas entre si, considerando o tamanho de cada solução obtida e seu tempo de execução.-
Descrição: dc.descriptionFor a graph G = (V, E), the Minimum k-Dominating Set Problem consists of finding a minimum set S ⊆ V where each vertex v ∈ V belongs to S or has at least k neighbors in S. Since the problem is NP-hard, finding an exact solution has a high computational cost. This work presents six greedy heuristics based on vertices requirements, degrees, and combinations of both factors. The experiments were divided into two parts. The first one compares heuristic results with exact solutions of graphs with twenty, fifty, and a hundred vertices. The second part considers graphs with up to ten thousand vertices and compares each heuristic to the others, considering the costs of the solutions and the execution times.-
Descrição: dc.description43 p.-
Formato: dc.formatapplication/pdf-
Idioma: dc.languagept_BR-
Direitos: dc.rightsOpen Access-
Direitos: dc.rightsCC-BY-SA-
Palavras-chave: dc.subjectProblema da k-Dominação Mínima-
Palavras-chave: dc.subjectHeurísticas-
Palavras-chave: dc.subjectMétodo Guloso-
Palavras-chave: dc.subjectOtimização em Grafos-
Palavras-chave: dc.subjectCiência da Computação-
Palavras-chave: dc.subjectHeurística-
Palavras-chave: dc.subjectMinimum k-Dominating Set Problem-
Palavras-chave: dc.subjectHeuristics-
Palavras-chave: dc.subjectGreedy Method-
Palavras-chave: dc.subjectGraph Optimization-
Título: dc.titleUm estudo de heurísticas para o problema da k-Dominação-
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.