Eduardo Laber
PUC, Rio de Janeiro
Sexta-feira, 7 de dezembro de 2001 às 14 horas
anfiteatro Jacy Monteiro, IME-USP
Resumo:
Neste trabalho propomos uma nova abordagem para otimização de Consultas envolvendo Predicados Caros em Bancos de Dados Distribuídos. Esta nova abordagem conduz ao seguinte problema em Grafos Bipartidos. Dado um grafo bipartido G=(A \cup B, E), onde cada vértice é V ou F, deseja-se encontrar o mais rápido possível o conjunto das arestas V, aquelas cujas duas extremidades são ambos V. A única operação permitida neste modelo é testar se um vértice é V ou F e o tempo necessário para testar o vértice a é t(a). Apresentamos uma métrica para avaliação de algoritmos para resolução deste problema e discutimos o desempenho, segundo a métrica proposta, de alguns algoritmos determinísticose e randomizados
Este trabalho foi feito em conjunto com os pesquisadores R. Ravi (CMU), O. Parekh (CMU) e F. Porto (PUC-Rio)