Multiaspect graphs

• Ano de defesa: 2016
• Autor(a) principal: Wehmuth, Klaus
• Tipo de documento: Tese
• Tipo de acesso: Acesso aberto
• Idioma: eng
• Instituição de defesa: Laboratório Nacional de Computação Científica; Coordenação de Pós-Graduação e Aperfeiçoamento (COPGA); Brasil; LNCC; Programa de Pós-Graduação em Modelagem Computacional
• Palavras-chave em Português: Teoria dos grafos; Generalização de grafos; Redes multicamada; Graphs theory; Graphs generalization; CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO::MATEMATICA DA COMPUTACAO::MATEMATICA SIMBOLICA
• Link de acesso: https://tede.lncc.br/handle/tede/244

Recentemente, várias generalizações de grafos têm sido propostas para tratar problemas específicos envolvendo redes complexas variantes no tempo e redes complexas multi-camadas. Essas representações são propostas de maneira adequada para resolver problemas específicos, mas não são adequadas para uso geral e muitas vezes são incompatíveis entre si. Nesta tese apresentamos o conceito de Grafo Multi-Aspectos (MAG), que é uma generalização de grafos capaz de representar redes variantes no tempo, redes multi-camadas e redes simultaneamente multi-camadas e variantes no tempo. Mostramos que todo MAG é isomorfo a um grafo direcionado, o que é um importante resultado teórico. Com base nesse resultado é possível utilizar o conhecimento previamente obtido em teoria de grafos para problemas envolvendo MAGs. Dessa maneira, torna-se possível criar representações algébricas para MAGs com características semelhantes às encontradas nas representações para grafos orientados. Além disso, pode-se construir algoritmos básicos para MAGs através da adaptação de algoritmos conhecidos para grafos. Esses algoritmos básicos podem servir como modelo para criação de outros algoritmos para MAGs, bem como serem utilizados como primitivas para construção de novos algoritmos. Utilizando essas primitivas, introduzimos o conceito de centralidades em MAGs, bem como construimos algoritmos apropriadas para calcular essas centralidades.