کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
431122 688278 2008 17 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Approximate labelled subtree homeomorphism
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Approximate labelled subtree homeomorphism
چکیده انگلیسی

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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Discrete Algorithms - Volume 6, Issue 3, September 2008, Pages 480–496
نویسندگان
, , , ,