Multicortes minimax em grafos

                          Orlando Lee

                Sexta-feira, 15 de outubro de 2004

                  Auditório do IC, IC-1, 13:00hs

Resumo:

Seja G um grafo e T:={t1,t2,...,tk} um conjunto de vértices, chamados
terminais. 

Um multicorte (com respeito a T) de um grafo G é uma
partição U:={U1,U2,...,Uk} de V(G) tal que ti pertence a Ui para
i=1,2,...,k. 

Dado um multicorte U:={U1,U2,...,Uk} de G, denote por d(Ui) o
número de arestas com uma ponta em Ui e outra em V(G)-Ui, para
i=1,2,...,k. O valor do multicorte U é definido como

   val(U):= max d(Ui).
             i

O problema do MultiCorte MiniMax consiste em dados um grafo G e um
conjunto de terminais T, encontrar um multicorte em G com valor mínimo.

Svitkina e Tardos mostraram que esse problema é NP-difícil.
Nesta palestra apresentaremos um algoritmo de aproximação para o
problema com garantia de desempenho O(log^3 n) e discutiremos alguns
resultados correlatos.