Problema de alcançabilidade em grafos muito grandes: Aplicação, complexidade e algoritmos

Detalhes bibliográficos
Ano de defesa: 2019
Autor(a) principal: Rodrigo Ferreira da Silva
Orientador(a): Não Informado pela instituição
Banca de defesa: Não Informado pela instituição
Tipo de documento: Tese
Tipo de acesso: Acesso aberto
Idioma: por
Instituição de defesa: Universidade Federal de Minas Gerais
UFMG
Programa de Pós-Graduação: Não Informado pela instituição
Departamento: Não Informado pela instituição
País: Não Informado pela instituição
Palavras-chave em Português:
Link de acesso: http://hdl.handle.net/1843/SLSC-BBKFX9
Resumo: Given a directed acyclic graph G=(V,E) and two vertices u, v in V, the reachability problem is to answer if is it possible to reach v from u by transversing the edges of the graph. For very large graphs, with millions of vertices, it is infeasible to search the graph for each query and it is also infeasible to store the transitive closure of the graph since it is squared in terms of space. Then, scalable approaches aim to generate good indexes used to prune the search during its execution in the graph. In this work, we formalize the One-Sided Weak Dominance Drawing Problem which is already used informally in the literature to construct this kind of indexes and we also prove that this problem is NP-Complete. Next, we identify oportunities for improvement on main approaches for the problem. We propose a novel scalable approach called LYNX that uses a large number of topological sorts of the graph as a negative cut index without degrading the query time. A similar strategy is applied regarding the positive cut index. In addition, LYNX proposes a user-defined index size that enables the user to control the ratio between negative and positive cut depending on the expected query pattern. We show by computational experiments that LYNX outperforms the state-of-the-art approach in terms of query-time using the same index-size for graphs with high reachability ratio.