Detalhes bibliográficos
| Ano de defesa: |
2002 |
| Autor(a) principal: |
Gondo, Eduardo Kazuaki |
| Orientador(a): |
Não Informado pela instituição |
| Banca de defesa: |
Não Informado pela instituição |
| Tipo de documento: |
Dissertação
|
| Tipo de acesso: |
Acesso aberto |
| Idioma: |
por |
| Instituição de defesa: |
Biblioteca Digitais de Teses e Dissertações da USP
|
| Programa de Pós-Graduação: |
Não Informado pela instituição
|
| Departamento: |
Não Informado pela instituição
|
| País: |
Não Informado pela instituição
|
| Palavras-chave em Português: |
|
| Link de acesso: |
https://teses.usp.br/teses/disponiveis/45/45134/tde-20210729-130244/
|
Resumo: |
O Problema de Steiner em grafos consiste em encontrar, em um grafo com custos nas arestas, uma árvore de custo mínimo contendo um dado conjunto de vértices. Esse problema tem um papel central na área de algoritmos de aproximação e diversas de suas variantes têm aplicações, por exemplo, em projeto de redes de comunicação. Neste trabalho apresentamos um estudo de vários algoritmos de aproximação para este problema. Os algoritmos escolhidos baseiam-se na utilização de árvores k-restritas e formam uma série, cada um deles tendo explorado melhor uma idéia introduzida pelo anterior. Todos eles foram projetados durante a última década, sendo o mais recente, o melhor algoritmo de aproximação para o problema até o momento em termos de razão de aproximação |
