Workshop on Approximation Algorithms and Graph Theory

Data: de 14 a 16 de fevereiro de 2003.

Local: Hotel Rancho Silvestre, Embú/SP.

Participantes

• Paulo Feofiloff
• Cristina Gomes Fernandes
• Carlos Eduardo Ferreira
• José Coelho de Pina Jr
• Yoshiko Wakabayashi

• Orlando Lee
• Flávio Keidi Miyazawa

• Evandro C. Bracht
• Daniel Morgato Martin
• Luis A. A. Meira
• Eduardo C. Xavier

Problemas discutidos

• Min Ratio Cut: aproximações para o problema de encontrar um corte C em um grafo com pesos w nas arestas e d nos vértices tq w(c)/(d(C)d(V-C)) é mínimo (Luis)
• Minimum connected dominating set: aproximações para o problema de encontrar uma árvore geradora com número máximo de folhas (Eduardo)
• Conjectura do Lovász que diz que um grafo conexo é bicrítico sse é o grafo completo (Daniel)
• Igualdades minimax: dicuts mínimos e conjuntos máximos de dijoins disjuntas (Paulo)
• Aproximações para o problema do subgrafo gerador k-aresta-conexo de peso médio mínimo (Cris)

Sponsored by the Ministry of Science and Technology (MCT) through Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq) under "Programa de Apoio a Núcleos de Excelência".