Seminário de Teoria da Computação e Combinatória
Título: A conjetura de Woodall: um resumo
Palestrante: Paulo Feofiloff
Local: Sala 267 do Bloco A
Data: sexta, 21 de outubro, às 14:00
A conjetura de Woodall afirma que todo grafo (orientado) G
satisfaz a minimax \nu(G) = \tau(G), sendo \nu(G) o número
máximo de junções mutuamente disjuntas e \tau(G) a cardinalidade
de um corte (orientado) mínimo de G. Aqui, uma junção é um
conjunto J de arestas tal que qualquer vértice é ligado a
qualquer outro por um caminho cujas arestas diretas estão em J.
Esta palestra pretende fazer um resumo do que se sabe sobre a
conjetura. Em particular, pretende comentar os trabalhos de
Cornuéjols e Guenin (2000 e 2002), Williams (2004), Shepherd
e Vetta (2005).
Para mais informações sobre o seminário de TCC, visite a página:
http://pronex-focos.incubadora.fapesp.br/portal/seminarios/
Forum