"Numeração-st em Grafos"
Amaury Antonio de Castro Junior

15/05/2000 - Segunda-feira
Horário: 17:00 h.
Local: Sala 2003

Resumo.
Dado um grafo G biconexo com n vértices e uma aresta {s,t} qualquer
em G. Os vértices de G podem ser numerados de 1 a n, de tal forma
que o vértice s recebe o número 1, o vértice t recebe o número n e
qualquer vértice, exceto s e t, é adjacente a um vértice de numeração
mais baixa e a um vértice de numeração mais alta. Esse esquema de
numeração é denominado numeração-st para G. Lempel, Even e
Cederbaum, em 1967, usaram este esquema de numeração como um
dos passos para um algoritmo eficiente de teste de planaridade. Even e
Tarjan, em 1976, reduziram o tempo deste algoritmo de O(mn) para
O(m+n), utilizando busca em profundidade em grafos.
Em 1986, Maon, Schieber e Vishkin, utilizaram a idéia do algoritmo
seqüencial de Even e Tarjan no desenvolvimento de um algoritmo
paralelo, no modelo PRAM CRCW, para o problema da numeração-st,
utilizando busca em decomposição em orelhas.

Neste seminário, iremos apresentar um visão geral do problema de
numeração-st em grafos, o algoritmo seqüencial de Even e Tarjan e,
por último, uma breve descrição de alguns problemas relacionados a
determinação de uma numeração-st em paralelo.