Banca de DEFESA: FERNANDO HENRIQUE SANCHES
Uma banca de DEFESA de MESTRADO foi cadastrada pelo programa.
DISCENTE : FERNANDO HENRIQUE SANCHES
DATA : 08/02/2019
HORA: 14:00
LOCAL: Sala 301, 3º andar do Bloco B, campus Santo André
TÍTULO:
Analysis of Decomposition Algorithms for the Tree Edit Distance Problem
PÁGINAS: 98
GRANDE ÁREA: Ciências Exatas e da Terra
ÁREA: Ciência da Computação
SUBÁREA: Teoria da Computação
ESPECIALIDADE: Análise de Algoritmos e Complexidade de Computação
RESUMO:
The Tree Edit Distance (TED) problem is a generalization of the Levenshtein Distance (String Edit Distance). In the TED we are given two rooted, labelled trees A and B, and we want to know the minimum cost of a sequence of operations that transforms A
into B by inserting, deleting or relabelling nodes. In this work we analyze some algorithms of the family of Decomposition Algorithms: Zhang-Shasha’s, Klein’s, and Demaine’s. We revisit the proofs of some of their lemmas, aiming to bring a clearer version when possible. We also present a working implementation of Klein’s algorithm operating over Euler strings, as described in his original work.
MEMBROS DA BANCA:
Presidente - 1760938 - DANIEL MORGATO MARTIN
Interno - 1934625 - JESUS PASCUAL MENA CHALCO
Externo à Instituição - DANIEL DE ANGELIS CORDEIRO - USP