Article ID Journal Published Year Pages File Type
431607 Journal of Discrete Algorithms 2015 8 Pages PDF
Abstract

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.

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