Um estudo da eficiência da autocentralidade no problema de isomorfismo de grafos

Página do item simplificado
dc.contributor.advisor-co1Rangel, Maria Cristina
dc.contributor.advisor1Boeres, Maria Claudia Silva
dc.contributor.authorBaroni, Marcos Daniel Valadão
dc.contributor.referee1Alvarenga, Arlindo Gomes de
dc.contributor.referee2Justel, Claudia Marcela
dc.date.accessioned2016-08-29T15:33:17Z
dc.date.available2016-07-11
dc.date.available2016-08-29T15:33:17Z
dc.date.issued2012-01-27
dc.description.abstractThis work treats the application of the eigenvector centrality in solving the Graph Isomorphism Problem. This property, taken from spectral graph theory, was used by Philippe Santos in [SANTOS 2010] to propose a spectral algorithm for solving this problem. An adaptation of the power method is proposed to compute the eigenvector centrality, producing a competitive version to the spectral algorithm of [SANTOS 2010]. Based on this adaptation, the efficiency of the eigenvector centrality in solving the problem is studied. In addition, it is proposed an iterative labeling algorithm, called Centrality Based Iterative Algorithm, which can be applied to any type of graph, including regular ones. Several tests are performed to compare the two proposed algorithms with some others well-known algorithms from literature, such as Nauty.eng
dc.description.resumoEste trabalho trata da aplicação da autocentralidade na resolução do Problema de Isomorfismo de Grafos. Esta propriedade, retirada da teoria espectral de grafos, foi utilizada por Philippe Santos em [SANTOS 2010] para a proposta de um algoritmo espectral para resolução deste problema. Uma adaptação do método das potências é proposta para o cálculo das autocentralidades produzindo uma versão competitiva do algoritmo espectral proposto em [SANTOS 2010]. Baseado nesta adaptação, é feito um estudo da eficiência da autocentralidade na resolução do Problema de Isomorfismo. Além disso, é Algoritmo de Rotulação Iterativa Baseado em Medidas de Centralidades, que pode ser aplicado a qualquer tipo de grafo, inclusive grafos regulares. Uma bateria de testes computacionais foi realizada para comparar os dois algoritmos propostos com alguns bemconhecidos na literatura, como o Nauty.
dc.formatText
dc.identifier.citationBARONI, Marcos Daniel Valadão. Um estudo da eficiência da autocentralidade no problema de isomorfismo de grafos. 2012. 73 f. Dissertação (Mestrado em Informática) - Universidade Federal do Espírito Santo, Centro Tecnológico, Vitória, 2012.
dc.identifier.urihttp://repositorio.ufes.br/handle/10/4257
dc.languagepor
dc.publisherUniversidade Federal do Espírito Santo
dc.publisher.countryBR
dc.publisher.courseMestrado em Informática
dc.publisher.departmentCentro Tecnológico
dc.publisher.initialsUFES
dc.publisher.programPrograma de Pós-Graduação em Informática
dc.rightsopen access
dc.subjectGraph theoryeng
dc.subjectIsomorphimseng
dc.subjectAlgorithmseng
dc.subjectEigenvectorseng
dc.subject.br-rjbnTeoria dos grafos
dc.subject.br-rjbnAlgoritmos
dc.subject.br-rjbnAutovetores
dc.subject.br-rjbnIsomorfismos (Matemática)
dc.subject.cnpqCiência da Computação
dc.subject.udc004
dc.titleUm estudo da eficiência da autocentralidade no problema de isomorfismo de grafos
dc.typemasterThesis
Arquivos
Pacote Original
Agora exibindo 1 - 1 de 1
Imagem de Miniatura
Nome:
Dissertação_5124_.pdf
Tamanho:
876.37 KB
Formato:
Adobe Portable Document Format
Descrição:
Baixar
Coleções
Mestrado em Informática