Correspondência inexata entre grafos - Freire, Alexandre S.; Ferreira, Carlos E. (Anais do Concurso de Teses e Dissertações da SBC (CTD-SBC); 2009: Anais do XXII Concurso de Teses e Dissertações, 2009)
Neste trabalho de mestrado estudamos o problema de correspondência inexata entre grafos que tem diversas variantes como descrevemos a seguir, com importantes aplicações, especialmente em processamento de imagens e visão computacional. Obtivemos resultados teóricos e práticos no mestrado: pudemos mostrar que uma variante do problema é NP-difícil mesmo quando os grafos da entrada são árvores. Através de formulações usando programação linear inteira e algoritmos de programação dinâmica pudemos resolver instâncias práticas de um problema de processamento de imagens com resultados promissores. Os resultados obtidos neste mestrado estão detalhados em dois artigos [Ferreira and Freire 2009, Freire et al. 2009].