کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
437679 | 690174 | 2015 | 15 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On the complexity of finding a largest common subtree of bounded degree
ترجمه فارسی عنوان
در پیچیدگی پیدا کردن بزرگترین زیرمجموعه مشترک از درجه محدود
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
فاصله ویرایش درخت، درختان بی نظیر، برنامه نویسی دینامیک، پیچیدگی پارامتریک
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
The largest common subtree problem is to find a bijective mapping between subsets of nodes of two input rooted trees of maximum cardinality or weight that preserves labels and ancestry relationship. The problem is known to be NP-hard for unordered trees. In this paper, we consider a restricted unordered case in which the maximum outdegree of a common subtree is bounded by a constant D . We present an O(nD)O(nD) time algorithm where n is the maximum size of two input trees, which improves a previous O(n2D)O(n2D) time algorithm. We also present an O((H2⋅22H−1⋅D2H)D−1poly(n))O((H2⋅22H−1⋅D2H)D−1poly(n)) time algorithm, where H is the maximum height of two input trees.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 590, 26 July 2015, Pages 2–16
Journal: Theoretical Computer Science - Volume 590, 26 July 2015, Pages 2–16
نویسندگان
Tatsuya Akutsu, Takeyuki Tamura, Avraham A. Melkman, Atsuhiro Takasu,