Computer Science – Computer Vision and Pattern Recognition
Scientific paper
2001-01-14
Computer Science
Computer Vision and Pattern Recognition
To appear in Journal of Algorithms
Scientific paper
A widely used method for determining the similarity of two labeled trees is to compute a maximum agreement subtree of the two trees. Previous work on this similarity measure is only concerned with the comparison of labeled trees of two special kinds, namely, uniformly labeled trees (i.e., trees with all their nodes labeled by the same symbol) and evolutionary trees (i.e., leaf-labeled trees with distinct symbols for distinct leaves). This paper presents an algorithm for comparing trees that are labeled in an arbitrary manner. In addition to this generality, this algorithm is faster than the previous algorithms. Another contribution of this paper is on maximum weight bipartite matchings. We show how to speed up the best known matching algorithms when the input graphs are node-unbalanced or weight-unbalanced. Based on these enhancements, we obtain an efficient algorithm for a new matching problem called the hierarchical bipartite matching problem, which is at the core of our maximum agreement subtree algorithm.
Kao Ming-Yang
Lam Tak-Wah
Sung Wing-Kin
Ting Hing-Fung
No associations
LandOfFree
An Even Faster and More Unifying Algorithm for Comparing Trees via Unbalanced Bipartite Matchings does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with An Even Faster and More Unifying Algorithm for Comparing Trees via Unbalanced Bipartite Matchings, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and An Even Faster and More Unifying Algorithm for Comparing Trees via Unbalanced Bipartite Matchings will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-194146