کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
431607 688594 2015 8 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
A top down algorithm for constrained tree inclusion
ترجمه فارسی عنوان
الگوریتم بالا پایین برای درج درخت درگیر
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی

Given two ordered labeled trees P and T, the constrained tree inclusion problem is to determine whether it is possible to obtain P from T   through a sequence of deleting degree-one or degree-two nodes. Valiente proposed a bottom up algorithm which solves the problem in O(nPnT)O(nPnT) time and O(nPnT)O(nPnT) space, where nPnP and nTnT are the numbers of the nodes in P and T   respectively. In this paper we present a top down matching algorithm which solves the problem in O(nPnT)O(nPnT) time but uses only O(nP+nT)O(nP+nT) space.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Discrete Algorithms - Volume 34, September 2015, Pages 62–69
نویسندگان
, ,