Article ID Journal Published Year Pages File Type
431122 Journal of Discrete Algorithms 2008 17 Pages PDF
Abstract

Given two undirected trees T and P, the Subtree Homeomorphism Problem is to find whether T has a subtree t that can be transformed into P by removing entire subtrees, as well as repeatedly removing a degree-2 node and adding the edge joining its two neighbors. In this paper we extend the Subtree Homeomorphism Problem to a new optimization problem by enriching the subtree-comparison with node-to-node similarity scores. The new problem, called Approximate Labelled Subtree Homeomorphism (ALSH), is to compute the homeomorphic subtree of T   which also maximizes the overall node-to-node resemblance. We describe an O(m2n/logm+mnlogn)O(m2n/logm+mnlogn) algorithm for solving ALSH on unordered, unrooted trees, where m and n are the number of vertices in P and T  , respectively. We also give an O(mn)O(mn) algorithm for rooted ordered trees and O(mnlogm)O(mnlogm) and O(mn)O(mn) algorithms for unrooted cyclically ordered and unrooted linearly ordered trees, respectively.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, , , ,