Paper Info
Title
Optimal mappings with minimum number of connected components in tree-to-tree comparison problems
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 + deg T2) × log2 (deg T1 + deg T2)).
Year
DOI
Venue
2003
10.1016/S0196-6774(03)00079-8
J. Algorithms
Keywords
Field
DocType
deg t1,connected component,tree-to-tree comparison problem,minimum number,unordered tree,sequential time,optimal mapping,stated problem,proposed algorithm,minimum cost mapping,deg t2,edit distance
Graph theory,Edit distance,Sequential time,Discrete mathematics,Combinatorics,Tree (graph theory),Generalization,Directed graph,Minimisation (psychology),Connected component,Mathematics
Journal
Volume
Issue
ISSN
48
2
0196-6774
Citations 
PageRank 
References 
0
0.34
10
Authors
2
Name
Order
Citations
PageRank
Pascal Ferraro17711.54
Christophe Godin212113.97