Approximate labelled subtree homeomorphism |
| |
Authors: | Ron Y Pinter Oleg Rokhlenko Dekel Tsur Michal Ziv-Ukelson |
| |
Institution: | aDepartment of Computer Science, Technion—Israel Institute of Technology, Haifa 32000, Israel;bDepartment of Computer Science, Ben Gurion University of the Negev, Beer-Sheva 84105, Israel |
| |
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) 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) algorithm for rooted ordered trees and O(mnlogm) and O(mn) algorithms for unrooted cyclically ordered and unrooted linearly ordered trees, respectively. |
| |
Keywords: | Tree similarity Approximate labelled matching |
本文献已被 ScienceDirect 等数据库收录! |
|