Paulo Feofiloff
IME-USP
Sexta-feira, 25 de outubro de 2002, 14:30
Sala 268, Bloco A, IME-USP
Resumo:
Uma _transversal_ em um grafo orientado é um conjunto de arcos (ou vértices) que intercepta todos os circuitos orientados do grafo. Em outras palavras, uma transversal em um grafo orientado G é um conjunto T de arcos (ou vértices) tal que G-T é acíclico.
A determinação de uma transversal mínima é um célebre problema NP-difícil. Esta palestra pretende fazer uma histórico superficial do problema, mencionando resultados de McCuaig, Cai et al., Seymour, Robertson, Thomas, Reed, Guenin, bem como os algoritmos de aproximação de Leighton, Rao e Seymour.