Árvores Geradoras Independentes

                           Orlando Lee

                 Sexta-feira, 15 de agosto de 2003
                  Auditório do IC (IC1), 13:00hs



Suponha que G seja um grafo e r um vertice de G.
Dizemos que duas arvores geradoras (enraizadas em r) T1 e T2 sao
independentes se para todo vertice v de G-r vale que:

o caminho de r a v em T1 e' internamente disjunto do
caminho de r a v em T2.

Nesta palestra discutiremos o seguinte problema: dado um grafo
k-conexo G e um vertice r de G, encontrar k arvores geradoras
independentes em G.

Descreveremos como os casos k=2 e k=3 podem ser resolvidos usando
tecnicas de "decomposicao em orelhas". Apresentaremos tambem uma vaga
ideia de como o caso k=4 foi resolvido recentemente por Curran, Yu e
Lee. Para k maior ou igual a 5, o problema continua em aberto.