@techreport{TR-IC-PFG-16-08,
   number = {IC-PFG-16-08},
   author = {Erick Ricardo {Mattos} and Eduardo C. Xavier},
   title = {{Algoritmos para Teste de Isomorfismo de Grafos}},
   month = {December},
   year = {2016},
   institution = {Institute of Computing, University of Campinas},
   note = {In Portuguese, 17 pages.
    \par\selectlanguage{brazil}\textbf{Resumo}
       O   objetivo  deste  trabalho  é  estudar  a  implementação  de 
       algoritmos que resolvam o problema de Isomorfismo em Grafos (em
       inglês  Graph  Isomorphism  ou  apenas GI). Não é conhecida uma
       solução polinomial para o problema geral, aquele que não assume
       alguma  propriedade  especial  para  o  grafo, bem como não foi
       provado que este problema é NP-Difícil e, assim, a complexidade
       deste  problema  ainda  está  em  aberto.  \par Foram estudados
       diferentes  métodos para a solução do problema, sendo escolhido
       para  implementação um método proposto por Weisfeiler e Lehman,
       conhecido  como  $k$-dim WL, que é capaz de resolver o problema
       em  tempo  linear no número de vértices, mas que, no pior caso,
       ainda  é  exponencial,  tanto  em  espaço como em tempo. \par O
       método  implementado  obteve  um  grande  speedup em relação ao
       método  trivial, que é tentar todas as possíveis permutações de
       vértices,  quando executados com grafos aleatórios. \par Apesar
       de  ser um método com complexidade exponencial, a implementação
       conseguiu   resolver  muito  casos  de  teste  em  baixo  tempo 
       computacional  e  com  rapidez,  mesmo  para  grafos  com muito
       vértices.  O  pior  caso  do método nos testes foi observado em
       grafos   regulares,  como  previsto  pela  análise  teórica  do 
       algoritmo.
  }
}