K-árvores de custo mínimo (2010)
- Authors:
- Autor USP: OSHIRO, MARCIO TAKASHI IURA - IME
- Unidade: IME
- Sigla do Departamento: MAC
- Assunto: OTIMIZAÇÃO COMBINATÓRIA
- Agências de fomento:
- Language: Português
- Abstract: Esta dissertação trata do problema da k-árvore de custo mínimo (k-MST): dados um grafo conexo G, um custo não-negativo Ce para cada aresta e, e um número inteiro positivo k, encontrar uma árvore com k vértices que tenha custo mínimo. O kMST é problema NP-difícil e portanto não se conhece um algoritmo polinomial para resolvê-lo. Nesta dissertação discutimos alguns casos em que é possível resolver o problema em tempo polinomial. Também são estudados algoritmos de aproximação para o kMST. Entre os algoritmos de aproximação estudados, apresentamos a 2-aproximação desenvolvida por Naveen Garg, que atualmente é o algoritmo com melhor fator de aproximação.
- Imprenta:
- Data da defesa: 11.06.2010
-
ABNT
OSHIRO, Marcio Takashi Iura; PINA JÚNIOR, José Coelho de. K-árvores de custo mínimo. 2010.Universidade de São Paulo, São Paulo, 2010. Disponível em: < http://www.teses.usp.br/teses/disponiveis/45/45134/tde-28052012-091652 >. -
APA
Oshiro, M. T. I., & Pina Júnior, J. C. de. (2010). K-árvores de custo mínimo. Universidade de São Paulo, São Paulo. Recuperado de http://www.teses.usp.br/teses/disponiveis/45/45134/tde-28052012-091652 -
NLM
Oshiro MTI, Pina Júnior JC de. K-árvores de custo mínimo [Internet]. 2010 ;Available from: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-28052012-091652 -
Vancouver
Oshiro MTI, Pina Júnior JC de. K-árvores de custo mínimo [Internet]. 2010 ;Available from: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-28052012-091652
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
