Optimal mappings with minimum number of connected components in tree-to-tree comparison problems |
| |
| Authors: | Pascal Ferraro Christophe Godin |
| |
| Affiliation: | a Université Bordeaux-1, LaBRI, 351, Cours de la Libération, 33405, Talence cedex, France;b UMR Cirad/Inra/Cnrs AMAP, TA40/PSII, Bd de la Lironde, 34398, Montpellier cedex 5, France |
| |
| Abstract: | In this paper we consider the problem of finding a minimum cost mapping between two unordered trees which induces a graph with a minimum number of connected components. The proposed algorithm is based on the generalization of an algorithm for computing an edit distance between trees, and it solves the stated problem in sequential time precisely in O(|T1|×|T2|×(degT1+degT2)×log2(degT1+degT2)). |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
