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. K-árvores de custo mínimo. 2010. Dissertação (Mestrado) – Universidade de São Paulo, São Paulo, 2010. Disponível em: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-28052012-091652. Acesso em: 20 maio 2024. -
APA
Oshiro, M. T. I. (2010). K-árvores de custo mínimo (Dissertação (Mestrado). 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. K-árvores de custo mínimo [Internet]. 2010 ;[citado 2024 maio 20 ] Available from: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-28052012-091652 -
Vancouver
Oshiro MTI. K-árvores de custo mínimo [Internet]. 2010 ;[citado 2024 maio 20 ] 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
