============================================================
   Seminário de Teoria da Computação e Combinatória (TCC)

============================================================

Título:      O problema de busca em árvores

            
Palestrante: Eduardo Sany Laber
             Departamento de Informática
             PUC do Rio de Janeiro

Hora e Data: 14h00m, segunda-feira, 02 de agosto de 2010

Local:       auditório do NUMEC

Resumo:


O problema  de busca em árvores consiste  em indentificar um
nó marcado em  uma árvore $T = (V,  E)$ utilizando consultas
as  arestas  de  $T$.   A  consulta  a  aresta  $e$  permite
descobrir em  qual das duas componentes de  $T\setminus e$ o
nó marcado se  encontra.  Quando o objetivo é  é minimizar o
número máximo de consultas, a estratégia de busca ótima pode
ser  encontrada em  tempo  linear [Onak  et. al.   FOCS'06],
[Mozes et. al. SODA'08] .

Uma variante do  problema de busca em árvores  é minimizar o
número médio de consultas para encontrar o nó marcado. Neste
caso temos uma  função $w : V \rightarrow  Z^+$ que define a
'probabilidade' de  um nó  da árvore ser  o nó  marcado.  Em
contraste com  a minimização do número  máximo de consultas,
em nossa pesquisa mostramos  que minimizar o número médio de
consultas é NP-COMPLETO para  classe de árvores com diâmetro
no  máximo  4 e  também  para  classe  de árvores  com  grau
limitado. Além disso,  desenvolvemos algoritmos com fator de
aproximação constante, uma FPTAS  para classe de árvores com
grau  limitado  e um  algoritmo  polinomial  para classe  de
árvores com diâmetro no máximo 3.

Nessa palestra discutimos os algoritmos desenvolvidos.  Esta
pesquisa foi realizada em parceria com Marco Molinaro (CMU),
Tobais Jacobs (National  Institute of Informatics, Tokyo.) e
Ferdinando Cicalese (U. Salerno)