Teoria espectral de grafos aplicada ao problema de isomorfismo de grafos

Página do item simplificado
dc.contributor.advisor-co1Boeres, Maria Claudia Silva
dc.contributor.advisor1Rangel, Maria Cristina
dc.contributor.authorSantos, Philippe Leal Freire dos
dc.contributor.referee1Abreu, Nair Maria Maia de
dc.contributor.referee2Catabriga, Lúcia
dc.date.accessioned2016-12-23T14:33:41Z
dc.date.available2011-03-18
dc.date.available2016-12-23T14:33:41Z
dc.date.issued2010-08-23
dc.description.abstractIn 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.eng
dc.description.resumoNeste trabalho investigamos a utilização de conceitos da Teoria Espectral de Grafos (TEG) a fim de auxiliar a construção de algoritmos que solucionem o Problema de Isomorfismo de Grafos (PIG). Três resultados teóricos que consideram informações do espectro e das centralidades de autovetor dos vértices dos grafos foram apresentados. Além disso, foi proposto um algoritmo para detecção de isomorfismo de grafos baseado em dois destes resultados. Por fim, apresentamos os resultados computacionais da comparação deste algoritmo com outros da literatura.
dc.formatText
dc.identifier.citationSANTOS, Philippe Leal Freire dos. Teoria espectral de grafos aplicada ao problema de Isomorfismo de Grafos. 2010. 70 f. Dissertação (Mestrado em Informática) - Universidade Federal do Espírito Santo, Centro Tecnológico, Vitória, 2010.
dc.identifier.urihttp://repositorio.ufes.br/handle/10/6388
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 isomorphism problemeng
dc.subjectSpectral graph theoryeng
dc.subjectEigenvector centralitieseng
dc.subjectProblema de isomorfismo de grafospor
dc.subjectTeoria espectral de grafospor
dc.subjectCentralidades de autovetorpor
dc.subject.br-rjbnTeoria dos grafos
dc.subject.br-rjbnTeoria espectral (Matemática)
dc.subject.br-rjbnIsomorfismos (Matemática)
dc.subject.br-rjbnAutovetores
dc.subject.cnpqCiência da Computação
dc.subject.udc004
dc.titleTeoria espectral de grafos aplicada ao problema de isomorfismo de grafos
dc.typemasterThesis
Arquivos
Pacote Original
Agora exibindo 1 - 1 de 1
Imagem de Miniatura
Nome:
Dissertacao de Philippe Leal Freire dos Santos.pdf
Tamanho:
1.17 MB
Formato:
Adobe Portable Document Format
Descrição:
Baixar
Coleções
Mestrado em Informática