Árvores k-restritas e aproximações para o Problema de Steiner em Grafos (2002)
- Authors:
- Autor USP: GONDO, EDUARDO KAZUAKI - IME
- Unidade: IME
- Sigla do Departamento: MAC
- Assunto: COMPUTABILIDADE E COMPLEXIDADE
- Language: Português
- Abstract: 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
- Imprenta:
- Data da defesa: 10.05.2002
-
ABNT
GONDO, Eduardo Kazuaki. Árvores k-restritas e aproximações para o Problema de Steiner em Grafos. 2002. Dissertação (Mestrado) – Universidade de São Paulo, São Paulo, 2002. Disponível em: https://teses.usp.br/teses/disponiveis/45/45134/tde-20210729-130244/. Acesso em: 02 out. 2024. -
APA
Gondo, E. K. (2002). Árvores k-restritas e aproximações para o Problema de Steiner em Grafos (Dissertação (Mestrado). Universidade de São Paulo, São Paulo. Recuperado de https://teses.usp.br/teses/disponiveis/45/45134/tde-20210729-130244/ -
NLM
Gondo EK. Árvores k-restritas e aproximações para o Problema de Steiner em Grafos [Internet]. 2002 ;[citado 2024 out. 02 ] Available from: https://teses.usp.br/teses/disponiveis/45/45134/tde-20210729-130244/ -
Vancouver
Gondo EK. Árvores k-restritas e aproximações para o Problema de Steiner em Grafos [Internet]. 2002 ;[citado 2024 out. 02 ] Available from: https://teses.usp.br/teses/disponiveis/45/45134/tde-20210729-130244/
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
