Método Guloso e o Algoritmo de Gomory-Hu

Resumo: Neste seminário descrevemos trabalho realizado em colaboração com Bert Gerards. Consideramos o problema de encontrar bases de peso mínimo em matróides com um número exponencial de elementos, como, por exemplo, o matróide dos cortes de um grafo. Aplicar o método guloso nesses matróides é inadequado, já que ordenar os elementos em relação aos seus pesos consome uma quantidade de tempo exponencial. Entretanto, uma perspectiva um pouco mais ampla do método guloso torna-se potencialmente aplicável também a matróides com um número exponencial de elementos. O método não funciona sempre, mas é aplicável, por exemplo, ao matróide dos cortes de um grafo. Neste caso, o método estabelece uma relação com o algoritmo de Gomory e Hu que encontra uma árvore fluxo-equivalente de um dado grafo.