Made available in DSpace on 2016-08-29T15:33:24Z (GMT). No. of bitstreams: 1
tese_9681_Ata de Defesa.pdf: 637986 bytes, checksum: 049a7d2723e6d0c1208ad9aad2eb9d0d (MD5)
Previous issue date: 2016-03-28 / Um dos problemas clássicos da Teoria de Grafos é o problema de isomorfismo
de grafos. Esse problema trata de determinar se, dado dois grafos, é possível definir
um mapeamento entre seus vértices de forma que sejam respeitadas as conexões
definidas por suas arestas. Um algoritmo proposto recentemente para resolver esse
problema é o IVL (Iterated Vertex Labelling) [Baroni (2012)].
O GROOVE (GRaph-based Object-Oriented VErification) é uma ferramenta
de verificação de modelos baseados em grafos que faz uso de algoritmos
de isomorfismo. No contexto do GROOVE, o problema de isomorfismo de grafos se
apresenta de uma maneira diferente do problema clássico: não se deseja determinar
se dois grafos são isomorfos, e sim se, dado um grafo, ele é isomorfo a algum dos
elementos de um conjunto de grafos.
Neste trabalho, propõe-se a adaptação do IVL para o GROOVE e a realiza-
ção de experimentos computacionais com o objetivo de determinar se essa adaptação
traz ganhos de performance para a ferramenta. Os resultados levam à conclusão de
que o IVL tem desempenho análogo ao algoritmo de isomorfismos que já está implementado
no GROOVE.
Além desses resultados, foi investigado em um cenário similar o uso de filtros
de não-isomorfismo, com a intenção de determinar o não-isomorfismo entre
dois grafos a um custo computacional baixo. Os resultados dos testes indicam que
essa abordagem é bastante promissora, sendo capaz de detectar não-isomorfismos
com eficiência de quase 100% , com tempos de execução bem mais baixos que os
performados pelo algoritmo atual do GROOVE quando executado nesse cenário
adaptado. / The graph isomorphism is a classical problem in Graph Theory, which consists
of determining if, given two graphs, it is possible to define a mapping between
their vertexes in a way so that the connection defined by their edges are respected.
An algorithm proposed recently to solve this problem is the IVL (Iterated Vertex
Labelling) [Baroni (2012)].
GROOVE (GRaph-based Object-Oriented VErification) is a graph-based
model checking tool which makes use of isomorphism algorithms. In GROOVE’s
context, the graph isomorphism problem is set differently from the classical problem:
they are not interested on determining if two graphs are isomorphic, instead, they
want to determine if, given a graph, it is isomorphic to one of the elements of a
graph set.
In this work, it’s proposed the IVL adaptation to GROOVE and computational
experiments in order to test if this new adapted algorithm brings performance
gains to the tool. It can be concluded from the results that IVL has a similar performance
compared to the current implementation in GROOVE.
Beyond those results, it was investigated in a similar framework the use
of non-isomorphism filters, intending to determine the non-isomorphism between
two graphs in a low computational cost. The test results point out that this is
a promising approach, being able to detect non-isomorphisms with almost 100%
efficiency, with a much lower running time when compared to current GROOVE
algorithm when executed in this framework.
| Identifer | oai:union.ndltd.org:IBICT/oai:dspace2.ufes.br:10/4302 |
| Date | 28 March 2016 |
| Creators | Anyzewski, Alessandra Silva |
| Contributors | Boeres, Maria Claudia Silva, Ochi, Luiz Satoru, Mauri, Geraldo Regis, Zambon, Eduardo |
| Publisher | Universidade Federal do Espírito Santo, Mestrado em Informática, Programa de Pós-Graduação em Informática, UFES, BR |
| Source Sets | IBICT Brazilian ETDs |
| Detected Language | English |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis |
| Format | text |
| Source | reponame:Repositório Institucional da UFES, instname:Universidade Federal do Espírito Santo, instacron:UFES |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.0019 seconds