Related Experiment Videos
The agreement metric for labeled binary trees
W Goddard1, E Kubicka, G Kubicki
1Department of Mathematics, University of Pennsylvania, Philadelphia.
Mathematical Biosciences
|October 1, 1994
Summary
This study introduces a quadratic algorithm to find the optimal agreement tree between two binary trees by pruning the fewest leaves. This method defines new metrics for comparing tree structures.
Area of Science:
- Computer Science
- Algorithmic Theory
- Data Structures
Background:
- Binary trees are fundamental data structures.
- Pruning involves removing leaves and simplifying tree structures.
- Agreement trees represent common structures between two trees.
Purpose of the Study:
- To develop an efficient algorithm for finding agreement trees.
- To define novel metrics based on agreement trees for tree comparison.
Main Methods:
- A quadratic algorithm is presented for computing the agreement tree.
- The algorithm involves pruning leaves from two input binary trees.
- The goal is to minimize the number of pruned leaves.
Main Results:
- An efficient quadratic-time algorithm for agreement tree computation.
- Definition of two new metrics derived from agreement trees.
- Demonstration of the algorithm's effectiveness in finding optimal agreement trees.
Conclusions:
- The proposed quadratic algorithm efficiently finds agreement trees.
- The new metrics offer a novel way to quantify tree similarity.
- This work contributes to the field of computational tree analysis.