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