Atenção: Todas as denúncias são sigilosas e sua identidade será preservada.
Os campos nome e e-mail são de preenchimento opcional
Metadados | Descrição | Idioma |
---|---|---|
Autor(es): dc.contributor | Silva, Maise Dantas da | - |
Autor(es): dc.contributor | http://lattes.cnpq.br/./2700813865300157 | - |
Autor(es): dc.contributor | Mafort, Rodrigo Lamblet | - |
Autor(es): dc.contributor | Silva, André Renato Villela da | - |
Autor(es): dc.contributor | http://lattes.cnpq.br/./4345875813789026 | - |
Autor(es): dc.contributor | Rocha, Danilo Artigas da | - |
Autor(es): dc.contributor | http://lattes.cnpq.br/./2404542754757428 | - |
Autor(es): dc.contributor | Andrade, Marcos Ribeiro Quinet de | - |
Autor(es): dc.contributor | http://lattes.cnpq.br/./8900303425878153 | - |
Autor(es): dc.creator | Rangel, Beatriz da Silva | - |
Data de aceite: dc.date.accessioned | 2024-07-11T17:45:18Z | - |
Data de disponibilização: dc.date.available | 2024-07-11T17:45:18Z | - |
Data de envio: dc.date.issued | 2023-01-02 | - |
Data de envio: dc.date.issued | 2023-01-02 | - |
Fonte completa do material: dc.identifier | http://app.uff.br/riuff/handle/1/27476 | - |
Fonte: dc.identifier.uri | http://educapes.capes.gov.br/handle/capes/756834 | - |
Descrição: dc.description | O 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.description | For 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.description | 43 p. | - |
Formato: dc.format | application/pdf | - |
Idioma: dc.language | pt_BR | - |
Direitos: dc.rights | Open Access | - |
Direitos: dc.rights | CC-BY-SA | - |
Palavras-chave: dc.subject | Problema da k-Dominação Mínima | - |
Palavras-chave: dc.subject | Heurísticas | - |
Palavras-chave: dc.subject | Método Guloso | - |
Palavras-chave: dc.subject | Otimização em Grafos | - |
Palavras-chave: dc.subject | Ciência da Computação | - |
Palavras-chave: dc.subject | Heurística | - |
Palavras-chave: dc.subject | Minimum k-Dominating Set Problem | - |
Palavras-chave: dc.subject | Heuristics | - |
Palavras-chave: dc.subject | Greedy Method | - |
Palavras-chave: dc.subject | Graph Optimization | - |
Título: dc.title | Um estudo de heurísticas para o problema da k-Dominação | - |
Tipo de arquivo: dc.type | Trabalho de conclusão de curso | - |
Aparece nas coleções: | Repositório Institucional da Universidade Federal Fluminense - RiUFF |
O Portal eduCAPES é oferecido ao usuário, condicionado à aceitação dos termos, condições e avisos contidos aqui e sem modificações. A CAPES poderá modificar o conteúdo ou formato deste site ou acabar com a sua operação ou suas ferramentas a seu critério único e sem aviso prévio. Ao acessar este portal, você, usuário pessoa física ou jurídica, se declara compreender e aceitar as condições aqui estabelecidas, da seguinte forma: