Poliedro das florestas

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:

  1. fluxos em redes (Ford e Fulkerson, Dinic, Edmonds e Karp);
  2. partição de grafos/matróides (Tutte, Nash-Williams, Edmonds);
  3. intersecção de polimatróides (Schönsleben, Lawler e Martel).

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

"Algoritmos para minimizar funções submodulares"?
Last modified: Tue Oct 21 17:32:33 BRST 2003