Informática

URI Permanente desta comunidade

http://repositorio.ufes.br/handle/10/17625
Programa de Pós-Graduação em Informática

Centro: CT
Telefone: (27) 4009 2324 R*5126
URL do programa: http://www.informatica.ufes.br/pt-br/pos-graduacao/PPGI

Navegar

Navegando Informática por Autor "Abreu, Nair Maria Maia de"

Agora exibindo 1 - 2 de 2
  • Nenhuma Miniatura disponível
    Item
    Teoria espectral de grafos aplicada ao problema de isomorfismo de grafos
    (Universidade Federal do Espírito Santo, 2010-08-23) Santos, Philippe Leal Freire dos; Boeres, Maria Claudia Silva; Rangel, Maria Cristina; Abreu, Nair Maria Maia de; Catabriga, Lúcia
    In this work we investigated the use of concepts from Spectral Graph Theory (SGT) to support the construction of algorithms that solve the Graph Isomorphism Problem (GIP). Three theoretical results which consider information from the spectrum of the graphs and from the eigenvector centralities were presented. Furthermore, an algorithm for detection of graph isomorphism based on two of these results was proposed. Finally, we present the computational results comparing this algorithm with others from literature.
  • Nenhuma Miniatura disponível
    Item
    Teoria espectral e o problema de isomorfismo de grafos regulares
    (Universidade Federal do Espírito Santo, 2011-08-29) Rodrigues, Diego Barcelos; Boeres, Maria Claudia Silva; Rangel, Maria Cristina; Alvarenga, Arlindo Gomes de; Abreu, Nair Maria Maia de
    Spectral Graph Theory (SGT) studies graph properties by graph representation matrix and its spectrum. A property from SGT, the eigencentrality, provides an important invariant to Graph Isomorphism Problem: if two graphs are isomorphic, they have proportional eigencentralities. However, this property can not be directly used for solving the Regular Graph Isomorphism Problem (RGIP), as every regular graph has the same eigencentralities. This work presents a strategy for solving the RGIP through the use of eigencentralities to prune the search tree and restricting the possibilities for mapping.