Yoshiko Wakabayashi
IME-USP
Sexta-feira, 20 de junho de 2007, 14:00
Anfiteatro do NUMEC
Resumo:
Num grafo, dizemos que uma aresta domina as arestas que incidem nela, e dizemos que um conjunto de arestas F é um conjunto dominante de arestas se as arestas de F coletivamente dominam todas as arestas do grafo. Estamos interessados no problema de encontrar, num dado grafo com pesos nas arestas, um conjunto dominante de arestas de peso mínimo. Yannakakis e Gavril mostraram que este problema é NP-difícil mesmo no caso em que o grafo é planar ou bipartido de grau máximo 3. Apresentaremos um algoritmo de 2-aproximação para este problema, obtido por Fujito e Nagamochi em 2002. A abordagem é baseada numa descrição linear (não tão) relaxada do poliedro naturalmente associado ao problema. Mencionaremos também outros resultados relacionados a este problema.