José Coelho de Pina
IME-USP
Sexta-feira, 17 de outubro de 2003, 14:00
Sala 266, Bloco A, IME-USP
Resumo:
Descreveremos o algoritmo fortemente polinomial de Cunningham que recebe um grafo (V,E) e um vetor x indexado por E e decide se x está no poliedro das florestas de (V,E).
Pergunta: Qual a graça nisto?
Resposta: Bem, o algoritmo parece ser uma combinação interessante de técnicas em:
Além disso, estas técnicas foram estendidas pelo próprio Cunningham para projetar um algoritmo combinatório pseudo-polinomial para minimizar funções submodulares. Finalmente, inspirados pelos métodos de Cunningham, foram projetados dois algoritmos combinatórios fortemente polinomiais para minimizar funções submodulares (Iwata, Fleischer e Fujishige, Schrijver).
Pergunta: Hein, que? Desculpe. Você estava falando alguma coisa?
Resposta: Não ...
P.S. A propósito, tem alguém ai interessado em escrever uma dissertação de mestrado em