In diverse applications relying on tree-structured data, can we efficiently determine the similarities between trees? This research addresses the problem of finding the smallest supertree under minor containment, a method for measuring similarity between trees. The findings present an algorithm for trees of bounded degree. This study focuses on supertrees under the general mapping of minor containment, a generalization of subgraph isomorphism and topological embedding. Because it is NP-complete to find whether or not G is a minor of H, even for genreal trees, the research focuses on trees of bounded degree. The study obtains an O(n3) algorithm which determines the smallest tree T such that both of the input trees are minors of T, even when the trees are assumed to be unrooted and unordered. By focusing on trees of bounded degree, we obtain an O(n3) algorithm which determines the smallest tree T such that both of the input trees are minors of T, even when the trees are assumed to be unrooted and unordered. This research provides a valuable tool for analyzing tree-structured data in various fields.
Published in the International Journal of Foundations of Computer Science, this research is well-suited to the journal's focus on theoretical computer science and algorithmic analysis. The paper's exploration of supertrees and minor containment contributes to the journal's coverage of fundamental problems in computer science.