Dissertação
A graph algorithm library based on compact data structures EVALUATED
Abordamos o problema de representação de grafos dinâmicos usando k2-trees. A estrutura de dados k2-tree é uma das estruturas de dados sucintas propostas para representar grafos estáticos e relações binárias em geral. Baseia-se em representações compactas de vetores de bits estáticos. Ao adicionar dinamismo às estruturas de dados compactas estáticas, também podemos representar grafos dinâmicos. No entanto, esta abordagem sofre de um problema bem conhecido da indexação dinâmica compactada, istoé o problema de manter uma coleção em mudança de modo a que possamos consultar a estrutura de dados de forma eficiente. Neste trabalho, apresentamos uma implementação baseada na k2-tree que segue, em vez disso, as ideias de Munro para contornar esta questão. Refatorizámos eextendemos o trabalho de Coimbra construindo uma biblioteca em C++. Esta biblioteca inclui iteradoresde arestas, nós e de vizinhança eficientes, bem como alguns algoritmos ilustrativos. Também incluímos um estudo sobre a operação de adição proposta inicialmente por Munro. Os nossos resultados experimentais mostram que nossa implementação é competitiva na prática.
janeiro 13, 2021, 18:0
Publicação
Obra sujeita a Direitos de Autor
Orientação
ORIENTADOR
Alexandre Paulo Lourenço Francisco
Departamento de Engenharia Informática (DEI)
Professor Associado