Projetos de Pesquisa

 

Foto de perfil

Sebastián Alberto Urrutia

Ciências Exatas e da Terra

Ciência da Computação
  • alcançabilidade em grafos muito grandes
  • Dados um grafo direcionado acíclico $G=(V,E)$ e dois vértices quaisquer $u, v \in V$, o problema de alcançabilidade consiste em responder se a partir de $u$ é possível alcançar $v$ percorrendo as arestas do grafo. Para grafos muito grandes, com milhoes de vértices, não é prático realizar uma busca no grafo a cada consulta ou armazenar o fecho transitivo completo já que o espaço necessário é da ordem de $O(|V|^2)$. Abordagens intermediárias geram índices para efetuar cortes negativos e positivos durante a execução das consultas. Neste projeto de pesquisa, formalizamos e atacamos problemas relacionados à geração e uso destes índices. Uma abordagem promisora para a obtenção de índices se baseia no computo de ordenações topológicas do grafo. Esse tipo de abordagens usam o fato de que se o vétice $u$ aparece depois do vértice $v$ em alguma ordenação topológica então pode-se deduzir que $u$ não alcança $v$. No tratamento dessa e outras abordagens aparecem problemas interessantes tanto teóricos (complexidade, aproximabilidade, etc) quanto práticos (tempo e espaço necessários para construção dos índices, tempo de consulta, etc.). O principal objetivo deste projeto de pesquisa é a geração de uma nova abordagem de criação de índices que supere em desempenho o estado da arte do problema.
  • Universidade Federal de Minas Gerais - MG - Brasil
  • 18/02/2019-28/02/2022