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, André Renato Villela da | - |
Autor(es): dc.contributor | Rocha, Danilo Artigas da | - |
Autor(es): dc.contributor | Silva, Maise Dantas da | - |
Autor(es): dc.creator | Menezes, Sandro André de | - |
Data de aceite: dc.date.accessioned | 2024-07-22T13:56:17Z | - |
Data de disponibilização: dc.date.available | 2024-07-22T13:56:17Z | - |
Data de envio: dc.date.issued | 2024-07-12 | - |
Data de envio: dc.date.issued | 2024-07-12 | - |
Fonte completa do material: dc.identifier | https://app.uff.br/riuff/handle/1/33285 | - |
Fonte: dc.identifier.uri | http://educapes.capes.gov.br/handle/capes/823333 | - |
Descrição: dc.description | Este 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.description | This 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.description | 21 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 | K-Dispersão | - |
Palavras-chave: dc.subject | Programação Linear | - |
Palavras-chave: dc.subject | Programação Inteira | - |
Palavras-chave: dc.subject | Tópicos Teoria e Algoritmos em Grafos (TAG) | - |
Palavras-chave: dc.subject | Otimização Combinatória (OC) | - |
Palavras-chave: dc.subject | K-Dispersion | - |
Palavras-chave: dc.subject | Linear Programming | - |
Palavras-chave: dc.subject | Integer Programming | - |
Palavras-chave: dc.subject | Paper topics Graph Theory and Algorithms (GTA) | - |
Palavras-chave: dc.subject | Combinatorial Optimization (CO) | - |
Título: dc.title | Um método guloso de simplificação para o problema da K-Dispersão discreta em grafos | - |
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: