k-árvores de custo mínimo / Minimum cost k-trees
AUTOR(ES)
Marcio Takashi Iura Oshiro
FONTE
IBICT - Instituto Brasileiro de Informação em Ciência e Tecnologia
DATA DE PUBLICAÇÃO
11/06/2010
RESUMO
Esta dissertação trata do problema da k-árvore de custo mínimo (kMST): dados um grafo conexo G, um custo não-negativo c_e 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 é um 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.
ASSUNTO(S)
algoritmos de aproximacao approximation algorithms Árvore geradora mínima combinatorial optimization k-mst k-mst minimum cost spanning tree otimização combinatória
Documentos Relacionados
- A compact code for k-trees
- O problema da arvore de custo minimo com k arestas:: reformulações e relaxação lagrangeana
- Problemas de fluxo de custo minimo em redes de custo concavo
- MODELS AND ALGORITHMS FOR THE DIAMETER CONSTRAINED MINIMUM SPANNING TREE PROBLEM
- Multi-K: a routing protocol for wireless sensor networks using partial spanning trees