• JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
 
  Bookmark and Share
 
 
Dissertação de Mestrado
DOI
https://doi.org/10.11606/D.45.2002.tde-20210729-130244
Documento
Autor
Nome completo
Eduardo Kazuaki Gondo
E-mail
Unidade da USP
Área do Conhecimento
Data de Defesa
Imprenta
São Paulo, 2002
Orientador
Título em português
Árvores k-restritas e aproximações para o Problema de Steiner em Grafos
Palavras-chave em português
Computabilidade E Complexidade
Resumo em português
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
Título em inglês
not available
Resumo em inglês
not available
 
AVISO - A consulta a este documento fica condicionada na aceitação das seguintes condições de uso:
Este trabalho é somente para uso privado de atividades de pesquisa e ensino. Não é autorizada sua reprodução para quaisquer fins lucrativos. Esta reserva de direitos abrange a todos os dados do documento bem como seu conteúdo. Na utilização ou citação de partes do documento é obrigatório mencionar nome da pessoa autora do trabalho.
Data de Publicação
2021-07-29
 
AVISO: Saiba o que são os trabalhos decorrentes clicando aqui.
Todos os direitos da tese/dissertação são de seus autores
CeTI-SC/STI
Biblioteca Digital de Teses e Dissertações da USP. Copyright © 2001-2024. Todos os direitos reservados.