Workshop in Combinatorics and Optimization
Data: de 14 a 16 de novembro de 2002.
Local: Hotel Fazenda Santa Helena, Mairiporã/SP.
| Horário |
|
14/11 |
15/11 |
16/11 |
| 8:00 |
|
café da manhã |
café da manhã |
café da manhã |
| 9:00 |
|
|
Arnaldo |
Lucchesi |
| 13:00 |
|
almoço |
almoço |
almoço |
| 15:00 |
|
Fábio |
|
reunião de encerramento |
| 19:30 |
|
jantar |
jantar |
|
| 21:00 |
|
Yoshiko |
|
|
| 24:00 |
|
estudo individual  |
estudo individual |
|
Problemas discutidos
- Problemas em árvores filogenéticas: cálculo da parcimônia, da
verossimilhança, problema dos quartetos.
- Problema do corte mínimo em partes de tamanhos dados: dado um
grafo G, com custo ce para cada
aresta e, e um vetor d de k inteiros
não-negativos cuja soma dos componentes é no máximo n
(onde n é o número de vértices de G), encontrar
uma partição
V0,...,Vk de
VG tal que
|Vi|=di e a
soma dos custos de todas as arestas entre partes
Vi e Vj, com 1
< i, j < k seja mínima.
- Problema da T-comparabilidade: dado um grafo G e um conjunto T
de vértices de G, decidir se existe uma orientação acíclica de G
que é transitiva nos vértices de T.
Provou-se durante o encontro que esse problema é NP-completo.
- Problema em grafos cobertos por emparelhamentos: dado um grafo,
decidir se tal grafo é um tijolo sólido.
Fotos
Last modified: Fri Feb 28 16:35:54 BRT 2003