Seminário de Teoria da Computação e Combinatória
Título: Empacotamento de T-pseudo-caminhos não-nulos
Palestrante: José Coelho de Pina
Local: Sala 267 do Bloco A
Data: sexta, 4 de novembro, às 14:00
Resumo:
Considere um grafo orientado com custos nos arcos e seja
T um subconjunto de seus vértices. Um T-pseudo-caminho
é uma sequência tal que
v_0,...,v_k são vértices distintos, v_0 e v_k estão em T
e a_i=(v_{i-1},v_i) ou a_i=(v_i,v_{i-1}) é um arco do grafo.
O custo de um pseudo-caminho é a soma dos custos dos arcos
"diretos" menos a soma dos custos dos arcos "inversos".
Chudnovsky, Geelen, Gerards, Goddyn, Lohman e Seymour
obtiveram um relação min-max para o número máximo de
T-pseudo-caminhos disjuntos de custos não-nulos.
Veremos algumas aplicações dessa relação min-max e
um pequeno esboço de sua demonstração.
Todos são bem-vindos!!
Para mais informações sobre o seminário de TCC, visite a página:
http://pronex-focos.incubadora.fapesp.br/portal/seminarios/
Fórum