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.